#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL << 62);
struct Edge {
int to;
ll p;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<map<int, vector<Edge>>> g(n + 1);
vector<map<int, ll>> sum(n + 1);
for (int i = 1; i <= m; ++i) {
int u, v, c;
ll p;
cin >> u >> v >> c >> p;
g[u][c].push_back({v, p});
g[v][c].push_back({u, p});
sum[u][c] += p;
sum[v][c] += p;
}
vector<ll> dp(n + 1, INF);
vector<map<int, ll>> dp2(n + 1);
using State = tuple<ll, int, int>; // dist, node, color (0 = normal)
priority_queue<State, vector<State>, greater<State>> pq;
dp[1] = 0;
pq.emplace(0, 1, 0);
while (!pq.empty()) {
auto [dist, u, c] = pq.top();
pq.pop();
if (c == 0) {
if (dist != dp[u]) continue;
for (auto &kv : g[u]) {
int color = kv.first;
ll total = sum[u][color];
for (auto &e : kv.second) {
// Case 1: recolor the other same-colored roads at u
ll nd1 = dist + total - e.p;
if (nd1 < dp[e.to]) {
dp[e.to] = nd1;
pq.emplace(nd1, e.to, 0);
}
// Case 2: recolor this road directly
ll nd2 = dist + e.p;
if (nd2 < dp[e.to]) {
dp[e.to] = nd2;
pq.emplace(nd2, e.to, 0);
}
// Case 3: keep a pending state for this color
auto it = dp2[e.to].find(color);
if (it == dp2[e.to].end() || dist < it->second) {
dp2[e.to][color] = dist;
pq.emplace(dist, e.to, color);
}
}
}
} else {
auto it = dp2[u].find(c);
if (it == dp2[u].end() || dist != it->second) continue;
auto git = g[u].find(c);
if (git == g[u].end()) continue;
ll total = sum[u][c];
for (auto &e : git->second) {
ll nd = dist + total - e.p;
if (nd < dp[e.to]) {
dp[e.to] = nd;
pq.emplace(nd, e.to, 0);
}
}
}
}
if (dp[n] >= INF / 2) cout << -1;
else cout << dp[n];
return 0;
}
