#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;
}
