/*
Created by ChrisDxng on 4/12/2026 2:47 PM
Problem Name: Robot
Problem Link: https://oj.uz/problem/view/JOI21_ho_t4
*/
#include <bits/stdc++.h>
#define Chris "test"
#define Fast std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
#define File(Chris) if(std::fopen(Chris".inp", "r")){std::freopen(Chris".inp", "r", stdin);std::freopen(Chris".out", "w", stdout);}
template<class X, class Y>bool maximize(X &x, const Y &y){if(x < y){x = y; return true;} else return false;}
template<class X, class Y>bool minimize(X &x, const Y &y){if(x > y){x = y; return true;} else return false;}
static constexpr long long mod = 1e9 + 7;
static constexpr int inf = (int) 1e5 + 5;
static constexpr long long INF = (long long) 1e18;
static constexpr int MAXN = (int) 1e3;
int numCrossing, numRoads;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
struct Edge {
int to, color;
long long cost;
};
void Inp(){
std::cin >> numCrossing >> numRoads;
}
void Solve() {
Inp();
std::vector<std::vector<Edge>> adj(numCrossing + 1);
std::vector<std::unordered_map<int, long long, custom_hash>> sumCost(numCrossing + 1);
for (int i = 0; i < numRoads; ++i) {
int u, v, c;
long long p;
std::cin >> u >> v >> c >> p;
adj[u].push_back({v, c, p});
adj[v].push_back({u, c, p});
sumCost[u][c] += p;
sumCost[v][c] += p;
}
for (int i = 1; i <= numCrossing; ++i) {
std::sort(adj[i].begin(), adj[i].end(), [](const Edge &a, const Edge&b) {
return a.color < b.color;
});
}
std::vector<long long> dp1(numCrossing + 1, INF);
std::vector<std::unordered_map<int, long long, custom_hash>> dp2(numCrossing + 1);
std::priority_queue<std::tuple<long long, int, int>, std::vector<std::tuple<long long, int, int>>, std::greater<std::tuple<long long, int, int>>> pq;
dp1[1] = 0;
pq.push({0, 1, 0});
while (!pq.empty()) {
auto [d, u, c] = pq.top();
pq.pop();
if (c == 0) { //no doubt
if (d > dp1[u]) continue;
if (u == numCrossing) {
std::cout << d << "\n";
return;
}
for (const auto& edge : adj[u]) {
int v = edge.to;
int color = edge.color;
long long cost = edge.cost;
long long S = sumCost[u][color];
//Case1: change color directly. Go to v clean, no doubt
if (dp1[v] > d + cost) {
dp1[v] = d + cost;
pq.push({dp1[v], v, 0});
}
//Case2: change another edge's color. Go to v clean, no doubt
if (dp1[v] > d + S - cost) {
dp1[v] = d + S - cost;
pq.push({dp1[v], v, 0});
}
//Case3: Doubt. Go to v and plus color's doubt
if (dp2[v].find(color) == dp2[v].end() || dp2[v][color] > d) {
dp2[v][color] = d;
pq.push({d, v, color});
}
}
}
else { //doubt
if (d > dp2[u][c]) continue;
Edge D = {0, c, 0};
auto it = std::lower_bound(adj[u].begin(), adj[u].end(), D, [](const Edge &a, const Edge &b) {
return a.color < b.color;
});
long long S = sumCost[u][c];
while (it != adj[u].end() && it->color == c) {
int v = it->to;
long long p = it->cost;
if (dp1[v] > d + S - p) {
dp1[v] = d + S - p;
pq.push({dp1[v], v, 0});
}
++it;
}
}
}
std::cout << -1 << "\n";
return;
}
signed main() {
Fast
File(Chris)
Solve();
return 0;
}
