#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
// Sử dụng long long cho khoảng cách để tránh tràn số
const long long INF = 1e16;
struct Edge {
int to, color, p, id;
};
struct State {
long long d;
int u, edge_id; // edge_id = -1: trạng thái tại đỉnh u, >=0: trạng thái đặc biệt tại cạnh
bool operator>(const State& other) const {
return d > other.d;
}
};
// Mảng lưu trữ dữ liệu
vector<Edge> adj[100005];
vector<pair<int, long long>> color_sums[100005];
long long dist_node[100005];
long long dist_special[200005];
int main() {
// Tối ưu hóa nhập xuất
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
// Lưu thông tin cạnh ban đầu
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];
// id chẵn: U->V, id lẻ: V->U
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});
}
// Tiền xử lý: Sắp xếp và tính tổng chi phí theo màu tại mỗi đỉ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 = (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++;
}
color_sums[i].push_back({adj[i][j].color, s});
j = k;
}
dist_node[i] = INF;
}
for (int i = 0; i < 2 * m; ++i) dist_special[i] = INF;
priority_queue<State, vector<State>, greater<State>> pq;
dist_node[1] = 0;
pq.push({0, 1, -1});
while (!pq.empty()) {
State top = pq.top();
pq.pop();
if (top.edge_id == -1) {
if (top.d > dist_node[top.u]) continue;
int u = top.u;
for (auto& e : adj[u]) {
// Tìm tổng chi phí của màu hiện tại tại đỉnh u
auto it = lower_bound(color_sums[u].begin(), color_sums[u].end(), make_pair(e.color, -1LL));
long long total_p = it->second;
// 1. Đổi màu duy nhất cạnh này (Strategy A)
if (dist_node[e.to] > top.d + e.p) {
dist_node[e.to] = top.d + e.p;
pq.push({dist_node[e.to], e.to, -1});
}
// 2. Đổi màu tất cả các cạnh khác cùng màu (Strategy B)
if (dist_node[e.to] > top.d + total_p - e.p) {
dist_node[e.to] = top.d + total_p - e.p;
pq.push({dist_node[e.to], e.to, -1});
}
// 3. Chuyển sang trạng thái đặc biệt: đến e.to nhưng chưa tính phí đổi màu tại u
if (dist_special[e.id] > top.d) {
dist_special[e.id] = top.d;
pq.push({dist_special[e.id], e.to, e.id});
}
}
} else {
// Trạng thái đặc biệt: đang ở đỉnh u, vừa đi qua cạnh top.edge_id
if (top.d > dist_special[top.edge_id]) continue;
int u = top.u;
// Cạnh vừa đi qua là top.edge_id, cạnh ngược lại của nó là top.edge_id ^ 1
// Cần lấy màu của cạnh này (có thể lưu trữ thêm hoặc tìm trong adj)
// Để tối ưu, ta đã lưu ID chẵn/lẻ. Cạnh đi từ u ra có màu ta cần.
// Truy xuất màu của cạnh id gốc:
int original_edge_idx = top.edge_id / 2;
int c = C[original_edge_idx];
auto it_sum = lower_bound(color_sums[u].begin(), color_sums[u].end(), make_pair(c, -1LL));
long long total_p = it_sum->second;
// Chỉ duyệt các cạnh có cùng màu c tại đỉnh u
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; });
while (it_adj != adj[u].end() && it_adj->color == c) {
// Không quay ngược lại cạnh vừa đi (id ^ 1)
if (it_adj->id != (top.edge_id ^ 1)) {
if (dist_node[it_adj->to] > top.d + total_p - it_adj->p) {
dist_node[it_adj->to] = top.d + total_p - it_adj->p;
pq.push({dist_node[it_adj->to], it_adj->to, -1});
}
}
it_adj++;
}
}
}
if (dist_node[n] >= INF) cout << -1 << endl;
else cout << dist_node[n] << endl;
return 0;
}
