#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
typedef long long ll;
using namespace std;
struct edge {
ll to, color, cost;
};
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});
vector<bool> vis(n + 1, false);
while (pq.size()) {
ll u = pq.top().second;
ll curr = -pq.top().first;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
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 v = e.to;
ll color = e.color;
ll cost = e.cost;
ll w = min(cost, sum[color] - cost);
if (dist[v] > curr + w) {
dist[v] = curr + w;
pq.push({-dist[v], v});
}
if (dist[v] > best[color] + sum[color] - cost) {
dist[v] = best[color] + sum[color] - cost;
pq.push({-dist[v], v});
}
}
for (edge e : adj[u]) {
sum[e.color] = 0;
best[e.color] = inf;
}
}
if (dist[n] == inf) return -1;
return dist[n];
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> m;
adj.resize(n + 1);
dist.resize(n + 1, inf);
sum.resize(m + 1);
best.resize(m + 1, inf);
for (ll i = 1; i<=m; ++i) {
ll u, v, color, cost;
cin >> u >> v >> color >> cost;
edge a = {v, color, cost};
edge b = {u, color, cost};
adj[u].push_back(a);
adj[v].push_back(b);
}
cout << dijkstra() << '\n';
return 0;
}
