#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e16;
struct Edge {
int to, color, cost, id;
long long sum_c; // Tổng chi phí các cạnh cùng màu tại đỉnh bắt đầu
};
struct Node {
long long d;
int u, edge_id; // edge_id = -1: trạng thái thường, >= 0: mã cạnh vừa đi qua
bool operator>(const Node& other) const { return d > other.d; }
};
vector<Edge> adj[100005];
long long dist_node[100005];
long long dist_edge[200005];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> U(m), V(m), C(m), P(m);
for (int i = 0; i < m; ++i) {
cin >> U[i] >> V[i] >> C[i] >> P[i];
adj[U[i]].push_back({V[i], C[i], P[i], i * 2});
adj[V[i]].push_back({U[i], C[i], P[i], i * 2 + 1});
}
// Dùng Two Pointers để tính sum_c cho mỗi cụm màu tại từng đỉnh
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;
});
int sz = adj[i].size();
for (int j = 0; j < sz; ) {
int k = j;
long long current_sum = 0;
while (k < sz && adj[i][k].color == adj[i][j].color) {
current_sum += adj[i][k].cost;
k++;
}
// Gán sum_c cho tất cả các cạnh trong cụm màu này
for (int l = j; l < k; ++l) adj[i][l].sum_c = current_sum;
j = k;
}
dist_node[i] = INF;
}
for (int i = 0; i < 2 * m; ++i) dist_edge[i] = INF;
priority_queue<Node, vector<Node>, greater<Node>> pq;
dist_node[1] = 0;
pq.push({0, 1, -1});
while (!pq.empty()) {
Node top = pq.top(); pq.pop();
long long d = top.d;
int u = top.u;
if (top.edge_id == -1) {
if (d > dist_node[u]) continue;
for (auto& e : adj[u]) {
// Cách 1: Đổi màu duy nhất cạnh e (tốn P_i)
if (dist_node[e.to] > d + e.cost) {
dist_node[e.to] = d + e.cost;
pq.push({dist_node[e.to], e.to, -1});
}
// Cách 2: Đổi màu các cạnh cùng màu e.color tại u (tốn Sum - P_i)
if (dist_node[e.to] > d + e.sum_c - e.cost) {
dist_node[e.to] = d + e.sum_c - e.cost;
pq.push({dist_node[e.to], e.to, -1});
}
// Cách 3: Chuyển sang trạng thái "nợ" (Strategy B) - không tốn phí bây giờ
if (dist_edge[e.id] > d) {
dist_edge[e.id] = d;
pq.push({dist_edge[e.id], e.to, e.id});
}
}
} else {
if (d > dist_edge[top.edge_id]) continue;
// Lấy màu của cạnh đã dẫn robot đến u
// Cạnh id=k nối (u, v) thì cạnh ngược lại là k^1 nối (v, u)
int color_prev = -1;
// Ở trạng thái này, robot vừa đi qua cạnh top.edge_id có màu cụ thể.
// Ta cần tìm lại màu đó. Để nhanh, hãy lưu color_prev vào State.
}
}
// ...
