#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; struct Edge { int v, u, c, p; }; int M = 100'010; vector<vector<pair<ll, ll>>> g(M); vector<map<int, int>> suma(M); vector<Edge> edges; ll inf = 1e18; vector<vector<ll>> dijkstra(int s) { vector<vector<ll>> dist(4*M, vector<ll>(2, inf)); priority_queue<pair<ll, pair<ll, ll>>> pq; int index = 0; for(auto e : edges) { if(e.v==s) { dist[index][0] = suma[s][e.c]-e.p; dist[index][1] = e.p; pq.push({-dist[index][0], {index, 0}}); pq.push({-dist[index][1], {index, 1}}); } ++index; } auto check = [&](int v, int msk, ll val) { if(dist[v][msk] > val) { dist[v][msk] = val; pq.push({-val, {v,msk}}); } }; while(pq.size()) { auto[dv, stat] = pq.top(); pq.pop(); auto[i,msk] = stat; Edge eg = edges[i]; dv*=-1; if(dist[i][msk]!=dv) continue; int v = eg.u; if(msk==1) { suma[v][eg.c] -= eg.p; } for(auto[u,idx] : g[eg.u]) { if((idx^1)==i) continue; Edge e = edges[idx]; if(e.c!=eg.c || msk==1) { check(idx, 1, dv + e.p); check(idx, 0, dv + suma[v][e.c] - e.p); } else { check(idx, 1, dv + e.p); } } if(msk==1) { suma[v][eg.c] += eg.p; } } return dist; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; cin >> n >> m; for(int i=0; i<m; ++i) { int a, b, c, p; cin >> a >> b >> c >> p; g[a].push_back({b,2*i}); g[b].push_back({a,2*i+1}); edges.push_back({a,b,c,p}); edges.push_back({b,a,c,p}); } for(int v=1; v<=n; ++v) { for(auto[u, i] : g[v]) { suma[v][edges[i].c] += edges[i].p; } } ll ans = inf; vector<vector<ll>> dist = dijkstra(1); int idx=0; for(auto e : edges) { if(e.u==n) { ans = min(ans, dist[idx][0]); ans = min(ans, dist[idx][1]); } ++idx; } if(ans==inf) cout << "-1\n"; else cout << ans << "\n"; return 0; }