// composite - yosupo #include <bits/stdc++.h> #define int long long #define ll long long #define vi vector<int> #define vb vector<bool> #define F(i, s, e) for(int i = s; i < e; i++) #define sp <<' '<< #define pii pair<int, int> #define fi first #define se second #define pb push_back #define vvi vector<vi> #define vpi vector<pii> #define vvpi vector<vpi> #define endl '\n' const ll mod = 998244353; using namespace std; const int N = 1e5+5; const ll inf = 1e15; struct Edge { int v, color, cost; bool paid = 0; }; vector<Edge> adj[N]; map<pii, int> colorcnt; map<pii, int> colorsum; void solve() { int n, m; cin >> n >> m; F(i, 0, m) { int _, __, ___, ____; cin >> _ >> __ >> ___ >> ____; _--, __--; adj[_].push_back({__, ___, ____}); adj[__].push_back({_, ___, ____}); colorcnt[{_, ___}]++; colorcnt[{__, ___}]++; colorsum[{_, ___}] += ____; colorsum[{__, ___}] += ____; } F(i, 0, n) { for(auto &edge : adj[i]) if(colorcnt[{i, edge.color}] > 1) { edge.paid = 1; } } #define State pair<int, pii> // node, {last_color, w} map<State, int> dist; priority_queue<pair<int, State>> pq; dist[{0, {-1, 0}}] = inf; pq.push({inf, {0, {-1, 0}}}); int ans = 0; while(!pq.empty()) { auto cur = pq.top(); pq.pop(); int dst = cur.fi, node = cur.se.fi, last_color = cur.se.se.fi, last_w = cur.se.se.se; if(dist[{node, {last_color, last_w}}] > dst) continue; if(node == n-1) ans = max(ans, dst); for(auto &edge : adj[node]) { /*int cost = edge.color == last_color && colorcnt[{node, last_color}] == 2 ? 0 : edge.cost; int new_last = cost ? edge.color : -1; if(dist[{edge.v, new_last}] < dst - cost) { dist[{edge.v, new_last}] = dst - cost; pq.push({dist[{edge.v, new_last}], {edge.v, new_last}}); }*/ int convertAll = colorsum[{node, edge.color}] - edge.cost; if(edge.color == last_color) convertAll -= last_w; State takestate = {edge.v, {edge.color, edge.cost}}; int takecost = dst - edge.cost; State passstate = {edge.v, {-1, 0}}; int passcost = min(dst, dst - convertAll); //cout << node sp edge.v sp edge.cost sp last_color sp last_w sp convertAll sp colorsum[{node, edge.color}] sp inf - takecost sp inf - passcost << endl; if(dist[passstate] < passcost) { dist[passstate] = passcost; pq.push({passcost, passstate}); } if(dist[takestate] < takecost) { dist[takestate] = takecost; pq.push({takecost, takestate}); } } } cout << (ans == 0 ? -1 : inf - ans) << endl; } int32_t main() { cin.tie(0); ios_base::sync_with_stdio(0); #ifdef Local freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int t = 1; //cin >> t; while(t--) solve(); }