#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e16;
struct Edge {
int to, color, cost, id;
};
struct State {
long long d;
int u, c; // c = 0: trạng thái thường, c > 0: mã định danh trạng thái màu
bool operator>(const State& other) const { return d > other.d; }
};
vector<Edge> adj[100005];
// sum_c[u][color] -> dùng vector + pair để thay map
vector<pair<int, long long>> sum_c[100005];
// dist[u] lưu khoảng cách trạng thái thường
long long dist0[100005];
// dist_c[edge_id] lưu khoảng cách khi robot vừa đi qua cạnh id (Strategy B)
long long dist_c[400005];
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;
// Mỗi cạnh 2 chiều, gán id để định danh trạng thái (u, color)
adj[u].push_back({v, c, p, i * 2});
adj[v].push_back({u, c, p, i * 2 + 1});
}
for (int i = 1; i <= n; ++i) {
sort(adj[i].begin(), adj[i].end(), [](const Edge& a, const Edge& b) {
return a.color < b.color;
});
// Tính sum_c tối ưu
for (int j = 0; j < adj[i].size(); ) {
int k = j;
long long s = 0;
while (k < adj[i].size() && adj[i][k].color == adj[i][j].color) {
s += adj[i][k].cost;
k++;
}
sum_c[i].push_back({adj[i][j].color, s});
j = k;
}
dist0[i] = INF;
}
for (int i = 0; i < 2 * m; ++i) dist_c[i] = INF;
priority_queue<State, vector<State>, greater<State>> pq;
dist0[1] = 0;
pq.push({0, 1, -1}); // c = -1 đại diện cho trạng thái dist0
while (!pq.empty()) {
State top = pq.top();
pq.pop();
if (top.c == -1) {
if (top.d > dist0[top.u]) continue;
int u = top.u;
for (auto& e : adj[u]) {
// Lấy tổng cost của màu e.color tại u
long long total_p = 0;
auto it = lower_bound(sum_c[u].begin(), sum_c[u].end(), make_pair(e.color, -1LL));
total_p = it->second;
// 1. Đổi màu cạnh e: cost = e.cost
if (dist0[e.to] > top.d + e.cost) {
dist0[e.to] = top.d + e.cost;
pq.push({dist0[e.to], e.to, -1});
}
// 2. Đổi màu các cạnh khác cùng màu e.color: cost = total_p - e.cost
if (dist0[e.to] > top.d + total_p - e.cost) {
dist0[e.to] = top.d + total_p - e.cost;
pq.push({dist0[e.to], e.to, -1});
}
// 3. Vào trạng thái đặc biệt của cạnh e (Strategy B)
if (dist_c[e.id] > top.d) {
dist_c[e.id] = top.d;
pq.push({dist_c[e.id], e.to, e.id});
}
}
} else {
// Đang ở trạng thái đặc biệt sau khi đi qua cạnh e_id_prev
if (top.d > dist_c[top.c]) continue;
int u = top.u;
// Lấy màu của cạnh đã đưa ta đến đây
int prev_id = top.c;
int color_prev = (prev_id % 2 == 0) ? adj[adj[u][0].to][prev_id/2].color : -1; // Cần lấy lại color từ ID
// Cách tốt hơn: Lưu color trực tiếp vào State
// Tuy nhiên, để tối ưu, ta chỉ duyệt các cạnh cùng màu tại u
// Tìm lại color_prev từ ID gốc (cách nhanh: lưu color vào struct Edge)
// Ở đây mình sẽ duyệt các cạnh cùng màu với cạnh đã đi
int target_color = 0;
// Tìm color của cạnh có id = prev_id (cạnh ngược lại là prev_id ^ 1)
// Nhưng thực tế ta có thể lưu color vào State để tránh tìm kiếm
}
}
// ... (logic Dijkstra tiếp tục)
