#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];
long long d[MXn];
void Dijkstra(void) {
for (int i = 1; i <= n; i++) d[i] = oo;
d[1] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
pq.emplace(0, 1);
while (sz(pq)) {
int u = pq.top().se, di = pq.top().fi;
pq.pop();
if (d[u] != di) continue;
for (auto V: adj[u]) {
int v = V.fi, c = V.se.fi, p = V.se.se;
if (d[v] > d[u] + min(tot[u][c] - p, p)) {
d[v] = d[u] + min(tot[u][c] - p, p);
pq.emplace(d[v], v);
}
}
}
}
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;
}
Dijkstra();
if (d[n] == oo) d[n] = -1;
cout << d[n];
return 0;
}
