#include <bits/stdc++.h> #define d1(x) cout << #x << " : " << x << endl << flush #define d2(x, y) cout << #x << " : " << x << " " << #y << " : " << y << endl << flush #define d3(x, y, z) cout << #x << " : " << x << " " << #y << " : " << y << " " << #z << " : " << z << endl << flush #define d4(x, y, z, a) cout << #x << " : " << x << " " << #y << " : " << y << " " << #z << " : " << z << " "<< #a << " : " << a << endl << flush #define arr(x) array <ll, x> #define ld long double #define ll long long #define int long long #define pb push_back #define endl '\n' #define lc v << 1 #define rc v << 1 | 1 using namespace std; const int INF = 1e12 + (35 / 10); // 35 ---> 36 const int MAXN = 2e5 + (35 / 10); // 35 ---> 36 vector <arr(5)> adj[MAXN]; vector <int> dp[MAXN]; map <arr(2), int> mp; int C[MAXN], P[MAXN]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for(int i = 0; i < n; i++) dp[i].pb(INF); for(int i = 1; i <= m; i++){ int u, v, c, p; cin >> u >> v >> c >> p; u--; v--; int eli = adj[u].size(); int esi = adj[v].size(); adj[u].pb({v, c, p, esi + 1, i}); adj[v].pb({u, c, p, eli + 1, i}); dp[u].pb(INF); dp[v].pb(INF); mp[{u, c}] += p; mp[{v, c}] += p; } // for(int i = 0; i <= adj[0].size(); i++) // dp[0][i] = 0; dp[0][0] = 0; set <arr(4)> s; s.insert({0, 0, 0}); while(!s.empty()){ auto [w, u, cool, id] = *s.begin(); s.erase(s.begin()); // d3(w, u, cool); for(int i = 0; i < adj[u].size(); i++){ auto [v, c, p, ind, ID] = adj[u][i]; int cost = p; if(dp[v][0] > w + cost){ dp[v][0] = w + cost; s.insert({dp[v][0], v, 0}); // d3(dp[v][ind], v, c); } if(cool != c){ cost = mp[{u, c}] - p; if(cool == 0 && C[id] == c) cost -= P[id]; if(dp[v][ind] > w + cost){ dp[v][ind] = w + cost; s.insert({dp[v][ind], v, c, ID}); // d3(dp[v][ind], v, c); } } // d3(i, u, v); // d1(2); } // d1(u); // cout << endl; } // cout << mp[{1, 3}] << " " << mp[{3, 3}] << endl; int ans = INF; for(auto u : dp[n - 1]) ans = min(ans, u); if(ans == INF) ans = -1; cout << ans << endl; } // Ey To Bahane! :_))) // -------------<3------------- // /* Magasan dor shirini: 1. MAXN 2. Input style 3. index or value? Masale In Ast! 4. MOD */