#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> using namespace std; /** * Cấu trúc lưu trữ thông tin cạnh: * to: Đỉnh đến * color: Màu của cạnh * cost: Chi phí thay đổi màu (P_i) */ struct Edge { int to, color, cost; }; struct State { long long dist; int u, color; // Priority queue cần min-heap bool operator>(const State& other) const { return dist > other.dist; } }; const long long INF = 1e18; vector<Edge> adj[200005]; map<int, long long> sum_cost[200005]; // Tổng P_i của các cạnh cùng màu tại mỗi đỉnh map<int, long long> dist[200005]; // dist[u][color] (color=0 là trạng thái mặc định) 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_cost[u][c] += p; sum_cost[v][c] += p; } priority_queue<State, vector<State>, greater<State>> pq; // Xuất phát từ đỉnh 1, trạng thái không màu (0) dist[1][0] = 0; pq.push({0, 1, 0}); while (!pq.empty()) { State top = pq.top(); pq.pop(); int u = top.u; int c = top.color; long long d = top.dist; if (d > dist[u][c]) continue; if (c == 0) { // Đang ở trạng thái bình thường tại đỉnh u for (auto& e : adj[u]) { // Cách 1: Đổi màu duy nhất cạnh này (cost = P_i) if (!dist[e.to].count(0) || dist[e.to][0] > d + e.cost) { dist[e.to][0] = d + e.cost; pq.push({dist[e.to][0], e.to, 0}); } // Cách 2: Đổi màu tất cả các cạnh khác cùng màu e.color (cost = Sum - P_i) long long cost2 = sum_cost[u][e.color] - e.cost; if (!dist[e.to].count(0) || dist[e.to][0] > d + cost2) { dist[e.to][0] = d + cost2; pq.push({dist[e.to][0], e.to, 0}); } // Cách 3: Chuyển sang trạng thái đặc biệt (v, c) để xử lý tiếp // Không mất phí lúc này, phí sẽ tính ở bước kế tiếp if (!dist[e.to].count(e.color) || 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: vừa đến u bằng cạnh có màu c (Strategy B) for (auto& e : adj[u]) { if (e.color == c) { // Tiếp tục đổi các cạnh còn lại của màu c (trừ cạnh vừa đi qua) long long cost = sum_cost[u][c] - e.cost; if (!dist[e.to].count(0) || dist[e.to][0] > d + cost) { dist[e.to][0] = d + cost; pq.push({dist[e.to][0], e.to, 0}); } } } } } if (!dist[n].count(0)) cout << -1 << endl; else cout << dist[n][0] << endl; return 0; }