#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
typedef long long ll;
using namespace std;
struct edge {
ll to, color, cost;
edge(){}
edge(ll a, ll b, ll c) {
to = a;
color = b;
cost = c;
}
};
const ll INF = 1e18;
vector<vector<edge>> adj;
vector<ll> dist, sum, best;
ll n, m;
ll dijkstra() {
dist[1] = 0;
priority_queue<pair<ll, ll>> pq;
pq.push({0, 1});
while (pq.size()) {
ll u = pq.top().second;
ll curr = -pq.top().first;
pq.pop();
if (curr != dist[u]) continue;
for (edge &e : adj[u]) {
sum[e.color] += e.cost;
best[e.color] = min(best[e.color], dist[e.to]);
}
for (edge e : adj[u]) {
ll to = e.to;
ll color = e.color;
ll w = e.cost;
ll tmp = min(0LL + w, sum[color] - w);
if (dist[to] > curr + tmp) {
dist[to] = curr + tmp;
pq.push({-dist[to], to});
}
if (dist[to] > best[color] + sum[color] - w) {
dist[to] = best[color] + sum[color] - w;
pq.push({-dist[to], to});
}
}
for (edge e : adj[u]) {
sum[e.color] = 0;
best[e.color] = INF;
}
}
if (dist[n] == INF) dist[n] = -1;
return dist[n];
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> m;
adj.resize(n + 1);
dist.resize(2 * n + 1);
sum.resize(m + 1);
best.resize(m + 1);
for (ll i = 1; i<=m; ++i) {
ll u, v, color, cost;
cin >> u >> v >> color >> cost;
edge a = edge(v, color, cost);
edge b = edge(u, color, cost);
adj[u].push_back(a);
adj[v].push_back(b);
}
for (ll i = 1; i<=n; ++i) dist[i] = INF;
for (ll i = 1; i<=m; ++i) best[i] = INF;
cout << dijkstra() << '\n';
return 0;
}
