#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 6e5 + 5;
int n, m;
vector<pair<int, long long>> g[maxn];
int eu[maxn], ev[maxn], ec[maxn], ep[maxn];
long long d[maxn];
long long s[maxn];
map<pair<int, int>, int> mp;
int total_id;
void add(int u, int c, int p) {
if (!mp.count(make_pair(u, c))) {
mp[make_pair(u, c)] = ++total_id;
}
s[mp[make_pair(u, c)]] += p;
}
void solve() {
cin >> n >> m;
total_id = n;
for (int i = 1; i <= m; ++i) {
cin >> eu[i] >> ev[i] >> ec[i] >> ep[i];
add(eu[i], ec[i], ep[i]);
add(ev[i], ec[i], ep[i]);
}
for (int i = 1; i <= m; ++i) {
int u = eu[i], v = ev[i];
int x = mp[make_pair(eu[i], ec[i])], y = mp[make_pair(ev[i], ec[i])];
// change (u, v, c) or every edge with same color except (u, v, c)
g[u].emplace_back(v, min((long long) ep[i], s[x] - ep[i]));
g[v].emplace_back(u, min((long long) ep[i], s[y] - ep[i]));
// go directly to (u, v, c)
g[u].emplace_back(y, 0);
g[v].emplace_back(x, 0);
// adding the cost of the previous edge in case we haven't
g[x].emplace_back(v, s[x] - ep[i]);
g[y].emplace_back(u, s[y] - ep[i]);
}
memset(d, 0x3f, sizeof(d));
d[1] = 0;
using T = pair<long long, int>;
priority_queue<T, vector<T>, greater<T>> pq;
pq.push(make_pair(0, 1));
while (!pq.empty()) {
long long dist; int u;
tie(dist, u) = pq.top();
pq.pop();
if (dist > d[u]) {
continue;
}
for (auto e:g[u]) {
int v; long long w;
tie(v, w) = e;
if (d[v] > d[u] + w) {
pq.push(make_pair(d[v] = d[u] + w, v));
}
}
}
cout << (d[n] > 1e17 ? -1 : d[n]);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
