#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<ll,int>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct edge{
int x;
int boja;
ll v;
};
ll maks = 1e9;
struct node{
int boja;
int x;
ll v;
};
bool operator < (const node &a, const node &b){
return a.v < b.v;
}
bool operator > (const node &a, const node &b){
return a.v > b.v;
}
int n,m;
map<int, vector<edge>> graf[100005];
map<int, ll> sb[100005];
ll dist[100005];
map<int,ll> dist2[100005];
bool cmp(edge a, edge b){
if(a.boja < b.boja)return 1;
return 0;
}
map<pii,bool>post;
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
maks *= maks;
cin >> n >> m;
// n = 1005;
// m = 2005;
ff(i,1,m){
int a,b,c,d;
// a = rnd()%n;
// b = rnd()%n;
// a++;
// b++;
// c = rnd()%m;
// c++;
// d = rnd()%1000000;
// if(post[{a,b}]){
// a = (rnd()%n) + 1;
// b = (rnd()%n) + 1;
// }
// post[{a,b}] = post[{b,a}] = 1;
cin >> a >> b >> c >> d;
graf[a][c].pb({b,c,d});
graf[b][c].pb({a,c,d});
sb[a][c] += d;
sb[b][c] += d;
}
priority_queue<node, vector<node>, greater<node> > pq;
pq.push({0,1,0});
dist[1] = 0;
ff(i,2,n)dist[i] = maks;
while(!pq.empty()){
node sta = pq.top();
int koji = sta.x;
int b = sta.boja;
ll vl = sta.v;
pq.pop();
int len = graf[koji].size();
if(len == 0)continue;
if(b){
if(vl != dist2[koji][b])continue;
}
else{
if(vl != dist[koji])continue;
}
if(b){
for(edge i : graf[koji][b]){
if(dist[i.x] > sb[koji][b] - i.v + vl){
dist[i.x] = sb[koji][b] - i.v + vl;
pq.push({0,i.x,dist[i.x]});
}
}
continue;
}
for(auto& i:graf[koji]){
for(edge j:i.yy){
ll d1 = min(j.v, sb[koji][i.xx] - j.v);
if(dist[j.x] > d1 + vl){
dist[j.x] = d1 + vl;
pq.push({0,j.x,dist[j.x]});
}
if(dist2[j.x].find(j.boja) == dist2[j.x].end() || dist2[j.x][j.boja] > vl){
dist2[j.x][j.boja] = vl;
pq.push({j.boja,j.x,vl});
}
}
}
}
if(dist[n] < maks)cout << dist[n] << "\n";
else cout << -1 << "\n";
return 0;
}
