#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define INF INT_MAX
#define all(x) x.begin(),x.end()
const int MOD = 1e9+7;
using namespace std;
struct T {
ll to, color, cost;
};
ll n, m;
vector<vector<T>> adj;
vector<ll> dist, sum, best;
const ll inf = 1e18;
void solve(){
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;
T a = {v, color, cost};
T b = {u, color, cost};
adj[u].push_back(a);
adj[v].push_back(b);
}
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 (T &e : adj[u]) {
sum[e.color] = 0;
best[e.color] = inf;
}
for (T &e : adj[u]) {
sum[e.color] += e.cost;
best[e.color] = min(best[e.color], dist[e.to]);
}
for (T &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 (T &e : adj[u]) {
sum[e.color] = 0;
best[e.color] = inf;
}
}
cout<< (dist[n] == inf ? -1 : dist[n])<<"\n";
}
int main()
{
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
