#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define sz(v) (int)(v).size()
using namespace std;
const int MXn = 100005;
const long long oo = 1e18;
const int MOD = 1e9 + 7;
int n, m;
vector<pair<int, pair<int, int>>> adj[MXn];
map<int, long long> tot[MXn];
map<int, pair<int, long long>> cost[MXn];
map<int, long long> d[MXn];
long long ans = oo;
void Dijkstra(void) {
d[1][-1] = 0;
priority_queue<pair<long long, pair<int, int>>, vector<pair<long long, pair<int, int>>>, greater<>> pq;
pq.push({0, {1, -1}});
while (sz(pq)) {
int u = pq.top().se.fi, last = pq.top().se.se, di = pq.top().fi;
pq.pop();
if (u == n) ans = min(ans, di);
if (d[u][last] != di) continue;
// cerr << u << ' ' << last << ' ' << d[u][last] << '\n';
for (auto V: adj[u]) {
int v = V.fi, c = V.se.fi, p = V.se.se;
if (last < 0) {
if (!d[v].count(-1) || d[v][-1] > d[u][-1] + tot[u][c] - p) {
d[v][-1] = d[u][-1] + tot[u][c] - p;
pq.push({d[v][-1], {v, -1}});
}
} else {
int lastc = cost[u][last].fi;
if (lastc != c) {
if (!d[v].count(-1) || d[v][-1] > d[u][last] + tot[u][c] - p) {
d[v][-1] = d[u][last] + tot[u][c] - p;
pq.push({d[v][-1], {v, -1}});
}
} else {
if (!d[v].count(-1) || d[v][-1] > d[u][last] + tot[u][c] - p - cost[u][last].se) {
d[v][-1] = d[u][last] + tot[u][c] - p - cost[u][last].se;
pq.push({d[v][-1], {v, -1}});
}
}
}
if (!d[v].count(u) || d[v][u] > d[u][last] + p) {
d[v][u] = d[u][last] + p;
pq.push({d[v][u], {v, u}});
}
}
}
}
signed main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for (int i = 1, a, b, c, p; i <= m; i++) {
cin >> a >> b >> c >> p;
adj[a].push_back({b, {c, p}});
adj[b].push_back({a, {c, p}});
if (!tot[a].count(c)) tot[a][c] = 0;
tot[a][c] += p;
if (!tot[b].count(c)) tot[b][c] = 0;
tot[b][c] += p;
cost[a][b] = cost[b][a] = {c, p};
}
Dijkstra();
cout << (ans == oo ? -1 : ans);
return 0;
}
