#include<bits/stdc++.h> #define fi first #define se second using namespace std; using ll = long long; const int N = 1e5; const int M = 2e5; const ll INF = 1e18; int n,m; struct edge{ int u,v,c,d; }a[M+5]; struct edg1{ int v,c,d; bool operator < (const edg1&other) const{ return v < other.v; } }; vector<edg1> g[N+5]; vector<pair<int,ll>> G[N+5]; ll dist[N+5]; int cost[M+5],cnt[M+5],lst[M+5]; void dji(int x){ for(int i = 1 ; i <= n ; ++i) dist[i] = INF; priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq; dist[x] = 0; pq.push({0,x}); while(!pq.empty()){ pair<ll,int> t = pq.top(); pq.pop(); ll w = t.fi; int u = t.se; // cout << u << ' ' << w << "!\n"; if(dist[u] > w) continue; for(pair<int,ll> i : G[u]) if(w + i.se < dist[i.fi]){ dist[i.fi] = w + i.se; pq.push({dist[i.fi],i.fi}); } } } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> m; for(int i = 1 ; i <= m ; ++i){ cin >> a[i].u >> a[i].v >> a[i].c >> a[i].d; g[a[i].u].push_back({a[i].v,a[i].c,a[i].d}); g[a[i].v].push_back({a[i].u,a[i].c,a[i].d}); } for(int i = 1 ; i <= n ; ++i){ // cout << i << ":\n"; for(edg1 j : g[i]){ cnt[j.c]++; } for(edg1 j : g[i]){ //cout << cnt[j.c] << ',' << j.v << '\n'; if(cnt[j.c] == 1) { // cout << i << ',' << j.v << ',' << 0 << '\n'; G[i].push_back({j.v,0}); //G[j.v].push_back({i,0}); } if(cnt[j.c] == 2) lst[j.c] = j.v; if(cnt[j.c] >= 2){ cost[j.c] += j.d; } } for(edg1 j : g[i]){ if(cnt[j.c] == 2 && j.v != lst[j.c]) { // cout << j.v << ',' << lst[j.c] << '.' << min(cost[j.c],j.d) << '\n'; G[j.v].push_back({lst[j.c],min(cost[j.c]-j.d,j.d)}); G[lst[j.c]].push_back({j.v,min(cost[j.c]-j.d,j.d)}); } if(cnt[j.c] >= 2){ G[i].push_back({j.v,min(j.d,cost[j.c]-j.d)}); } } for(edg1 j : g[i]){ cnt[j.c]--; lst[j.c] = cost[j.c] = 0; } } dji(1); if(dist[n] >= INF) cout << -1 << '\n'; else cout << dist[n]; return 0; }