#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const long long INF = 1e16;
struct Edge {
int to, color, cost, id;
};
struct Node {
long long d;
int u, edge_id, color;
// Priority queue min-heap
bool operator>(const Node& other) const {
return d > other.d;
}
};
// Cấu trúc để quản lý tổng chi phí theo màu tại mỗi đỉnh
struct ColorSum {
int color;
long long sum;
};
vector<Edge> adj[100005];
vector<ColorSum> sum_c[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;
for (int i = 0; i < m; ++i) {
int u, v, c, p;
cin >> u >> v >> c >> p;
// id chẵn cho chiều u->v, id lẻ cho chiều v->u
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) {
// 1. Sắp xếp cạnh theo màu để dùng Two Pointers
sort(adj[i].begin(), adj[i].end(), [](const Edge& a, const Edge& b) {
return a.color < b.color;
});
// 2. Tính tổng chi phí (sum_c) cho mỗi cụm màu tại đỉnh i
int sz = (int)adj[i].size();
for (int j = 0; j < sz; ) {
int k = j;
long long s = 0;
while (k < sz && 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;
}
dist_node[i] = INF;
}
for (int i = 0; i < 2 * m; ++i) dist_edge[i] = INF;
priority_queue<Node, vector<Node>, greater<Node>> pq;
// Xuất phát từ đỉnh 1
dist_node[1] = 0;
pq.push({0, 1, -1, 0}); // edge_id = -1 nghĩa là trạng thái tự do
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]) {
// Tìm sum_c của màu e.color tại u bằng binary search trên vector sum_c đã sort
auto it = lower_bound(sum_c[u].begin(), sum_c[u].end(), ColorSum{e.color, 0},
[](const ColorSum& a, const ColorSum& b) { return a.color < b.color; });
long long total_p = it->sum;
// Cách 1: Đổi màu duy nhất cạnh e (tốn P_i) -> v trạng thái tự do
if (dist_node[e.to] > d + e.cost) {
dist_node[e.to] = d + e.cost;
pq.push({dist_node[e.to], e.to, -1, 0});
}
// Cách 2: Đổi màu tất cả các cạnh khác cùng màu e.color tại u (tốn total_p - P_i)
if (dist_node[e.to] > d + total_p - e.cost) {
dist_node[e.to] = d + total_p - e.cost;
pq.push({dist_node[e.to], e.to, -1, 0});
}
// Cách 3: Giữ màu e, chuyển sang trạng thái "nợ" tại v
if (dist_edge[e.id] > d) {
dist_edge[e.id] = d;
pq.push({dist_edge[e.id], e.to, e.id, e.color});
}
}
} else {
// Trạng thái nợ: Vừa đến u bằng cạnh có màu top.color
if (d > dist_edge[top.edge_id]) continue;
int c = top.color;
// Tìm cụm màu c trong adj[u] đã được sort
auto it_adj = lower_bound(adj[u].begin(), adj[u].end(), Edge{0, c, 0, 0},
[](const Edge& a, const Edge& b) { return a.color < b.color; });
auto it_sum = lower_bound(sum_c[u].begin(), sum_c[u].end(), ColorSum{c, 0},
[](const ColorSum& a, const ColorSum& b) { return a.color < b.color; });
long long total_p = (it_sum != sum_c[u].end() && it_sum->color == c) ? it_sum->sum : 0;
// Chỉ xét các cạnh cùng màu c tại đỉnh u
while (it_adj != adj[u].end() && it_adj->color == c) {
// Tránh quay lại cạnh vừa đi (id của cạnh ngược lại là id ^ 1)
if (it_adj->id != (top.edge_id ^ 1)) {
if (dist_node[it_adj->to] > d + total_p - it_adj->cost) {
dist_node[it_adj->to] = d + total_p - it_adj->cost;
pq.push({dist_node[it_adj->to], it_adj->to, -1, 0});
}
}
it_adj++;
}
}
}
if (dist_node[n] >= INF) cout << -1 << endl;
else cout << dist_node[n] << endl;
return 0;
}
