#include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() struct Edge { int to, color, cost; }; struct Node { long long d; int u, c; bool operator>(const Node& other) const { return d > other.d; } }; const long long INF = 1e16; // Đủ lớn cho 2e5 * 1e6 vector<Edge> adj[100005]; map<int, long long> sum_c[100005]; map<int, long long> dist[100005]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < m; ++i) { int u, v, c, p; cin >> u >> v >> c >> p; adj[u].push_back({v, c, p}); adj[v].push_back({u, c, p}); sum_c[u][c] += p; sum_c[v][c] += p; } priority_queue<Node, vector<Node>, greater<Node>> pq; // dist[u][0] là khoảng cách ngắn nhất đến u mà không bị ràng buộc màu // dist[u][c] là khoảng cách ngắn nhất đến u thông qua cạnh màu c (chưa đổi màu c) dist[1][0] = 0; pq.push({0, 1, 0}); while (!pq.empty()) { Node top = pq.top(); pq.pop(); int u = top.u; int c = top.c; long long d = top.d; if (d > dist[u][c]) continue; if (c == 0) { for (auto& e : adj[u]) { // TH1: Đổi màu duy nhất cạnh (u, v) -> tốn p if (dist[e.to].find(0) == dist[e.to].end() || dist[e.to][0] > d + e.cost) { dist[e.to][0] = d + e.cost; pq.push({dist[e.to][0], e.to, 0}); } // TH2: Đổi màu tất cả các cạnh cùng màu c tại u (trừ cạnh này) -> tốn Sum - p long long cost_all = sum_c[u][e.color] - e.cost; if (dist[e.to].find(0) == dist[e.to].end() || dist[e.to][0] > d + cost_all) { dist[e.to][0] = d + cost_all; pq.push({dist[e.to][0], e.to, 0}); } // TH3: Đi vào trạng thái "đang xử lý màu c", không tốn phí ở bước này if (dist[e.to].find(e.color) == dist[e.to].end() || dist[e.to][e.color] > d) { dist[e.to][e.color] = d; pq.push({dist[e.to][e.color], e.to, e.color}); } } } else { // Đang ở trạng thái đặc biệt: đến u bằng màu c (của Strategy B) for (auto& e : adj[u]) { if (e.color == c) { // Chỉ đi tiếp các cạnh cùng màu c để hưởng ưu đãi phí long long cost_rem = sum_c[u][c] - e.cost; if (dist[e.to].find(0) == dist[e.to].end() || dist[e.to][0] > d + cost_rem) { dist[e.to][0] = d + cost_rem; pq.push({dist[e.to][0], e.to, 0}); } } } } } if (dist[n].find(0) == dist[n].end()) cout << -1 << endl; else cout << dist[n][0] << endl; return 0; }