#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<array<int, 3>>> adj(n);
for (int i = 0; i < m; i++) {
int u, v, color, cost;
cin >> u >> v >> color >> cost;
u--;
v--;
adj[u].push_back({ v, color, cost });
adj[v].push_back({ u, color, cost });
}
vector<long long> dist(n, -1);
priority_queue<array<long long, 3>, vector<array<long long, 3>>, greater<>> pq;
dist[0] = 0;
pq.push({0, 0, -1});
while (!pq.empty()) {
auto [d, u, p] = pq.top();
pq.pop();
if (dist[u] != d) continue;
map<int, long long> mp; // color to sum of cost
for (auto [v, color, cost] : adj[u]) {
if (v == p) {
continue;
}
mp[color] += cost;
}
for (auto [v, color, cost] : adj[u]) {
if (v == p) {
continue;
}
long long w = min(1LL * cost, mp[color] - cost);
if (dist[v] == -1 || dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v, u});
}
}
}
cout << dist[n - 1] << '\n';
}
