#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e16 + 66;
int32_t main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
map<ll, vector<array<ll, 3>>> g[N];
map<ll, ll> sum[N];
for (int i = 0;i < M;i ++) {
ll u, v, c, p;
cin >> u >> v >> c >> p;
-- u;
-- v;
g[u][c].push_back({v, c, p});
g[v][c].push_back({u, c, p});
sum[u][c] += p;
sum[v][c] += p;
}
map<ll, ll> dp[N];
vector<ll> dist(N, inf);
dist[0] = 0;
priority_queue<array<ll, 3>> pq;
pq.push({0, 0, 0});
while (pq.size() > 0) {
auto [val, u, c] = pq.top();
pq.pop();
ll tmp;
if (c == 0) {
if (dist[u] != -val) continue;
for (auto [fi, se] : g[u]) {
for (auto [v, _c, p] : se) {
tmp = sum[u][_c] - p - val;
if (tmp < dist[v]) {
dist[v] = tmp;
pq.push({-dist[v], v, 0});
}
tmp = p - val;
if (tmp < dist[v]) {
dist[v] = tmp;
pq.push({-dist[v], v, 0});
}
tmp = -val;
if (dp[v].count(_c) == 0 || tmp < dp[v][_c]) {
dp[v][_c] = tmp;
pq.push({-dp[v][_c], v, _c});
}
}
}
} else {
if (dp[u][c] != -val) continue;
for (auto [v, _c, p] : g[u][c]) {
tmp = sum[u][c] - p;
if (tmp - val < dist[v]) {
dist[v] = tmp - val;
pq.push({-dist[v], v, 0});
}
}
}
}
cout << (dist[N - 1] < inf ? dist[N - 1] : -1) << "\n";
}
