#include <iostream> #include <vector> #include <map> #include <queue> using namespace std; typedef long long ll; const ll INF = 1e18; struct Edge { int to, color; ll cost; int id; }; struct State { ll d; int u, color, edge_idx; bool operator>(const State& other) const { return d > other.d; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<vector<Edge>> adj(N + 1); vector<map<int, ll>> color_sum(N + 1); for (int i = 0; i < M; ++i) { int u, v, c; ll p; cin >> u >> v >> c >> p; adj[u].push_back({v, c, p, i}); adj[v].push_back({u, c, p, i}); color_sum[u][c] += p; color_sum[v][c] += p; } priority_queue<State, vector<State>, greater<State>> pq; vector<ll> dist(N + 1, INF); vector<ll> dist_edge(M, INF); dist[1] = 0; pq.push({0, 1, 0, -1}); while (!pq.empty()) { State top = pq.top(); pq.pop(); ll d = top.d; int u = top.u; // Type 1 State: Arrived at crossing u normally if (top.edge_idx == -1) { if (d > dist[u]) continue; for (auto& e : adj[u]) { // Option A: Change only this road's color if (dist[e.to] > d + e.cost) { dist[e.to] = d + e.cost; pq.push({dist[e.to], e.to, 0, -1}); } // Option B: Change all other roads of the same color ll cost_all_others = color_sum[u][e.color] - e.cost; if (dist[e.to] > d + cost_all_others) { dist[e.to] = d + cost_all_others; pq.push({dist[e.to], e.to, 0, -1}); } // Option C: Move to Type 2 state (carrying the color cost) if (dist_edge[e.id] > d) { dist_edge[e.id] = d; pq.push({dist_edge[e.id], e.to, e.color, e.id}); } } } // Type 2 State: Arrived at u, but color 'top.color' was "pre-paid" at previous node else { if (d > dist_edge[top.edge_idx]) continue; for (auto& e : adj[u]) { if (e.id == top.edge_idx) continue; if (e.color == top.color) { ll cost_remaining = color_sum[u][e.color] - e.cost; if (dist[e.to] > d + cost_remaining) { dist[e.to] = d + cost_remaining; pq.push({dist[e.to], e.to, 0, -1}); } } } } } if (dist[N] == INF) cout << -1 << endl; else cout << dist[N] << endl; return 0; }