#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
typedef long long ll;
using namespace std;
struct edge {
ll to, color, cost;
};
ll n, m;
vector<vector<edge>> adj;
vector<ll> dist, sum, best;
const ll inf = 1e18;
ll dijkstra() {
priority_queue<pair<ll, ll>> pq;
dist[1] = 0;
pq.push({0, 1});
vector<bool> visited(n + 1, false);
while (!pq.empty()) {
ll u = pq.top().second;
ll curr = -pq.top().first;
pq.pop();
if (visited[u]) continue;
visited[u] = true;
for (edge &e : adj[u]) {
sum[e.color] = 0;
best[e.color] = inf;
}
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 color = e.color;
ll v = e.to;
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] - w) {
dist[v] = best[color] + sum[color] - w;
pq.push({-dist[v], v});
}
}
for (edge &e : adj[u]) {
sum[e.color] = 0;
best[e.color] = inf;
}
}
return (dist[n] == inf ? -1 : dist[n]);
}
int main() {
cin >> n >> m;
adj.resize(n + 1);
dist.resize(n + 1, inf);
best.resize(m + 1, inf);
sum.resize(m + 1, 0);
for (ll i = 0; 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';
}
