#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for(int i = a; i >= (int)b; i--)
#define fi first
#define se second
const int N = 1E5 + 5;
int n, m;
vector <array <int, 3>> g[N];
map <int, long long> sumC[N];
map <int, long long> dp[N];
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define ko "kieuoanh"
if (fopen(ko".inp", "r")) {
freopen(ko".inp", "r", stdin); freopen(ko".out", "w", stdout);
}
cin >> n >> m;
FOR(i, 1, m) {
int u, v, c, p; cin >> u >> v >> c >> p;
sumC[u][c]+= p;
sumC[v][c]+= p;
g[u].push_back({c, v, p});
g[v].push_back({c, u, p});
}
FOR(i, 1, n) sort(g[i].begin(), g[i].end());
#define bg array <long long, 3>
priority_queue <bg, vector <bg>, greater <bg>> pq;
pq.push({dp[1][0] = 0, 1, 0});
while (!pq.empty()) {
int u = pq.top()[1], t = pq.top()[2];
long long cost = pq.top()[0];
pq.pop();
if (cost > dp[u][t]) continue;
if (t == 0) {
for (auto it : g[u]) {
int c = it[0], v = it[1], p = it[2];
if (dp[v].count(0) == 0) dp[v][0] = 1e18;
if (dp[v].count(c) == 0) dp[v][c] = 1e18;
if (dp[v][0] > cost + min(sumC[u][c] - p, 1LL * p)) {
dp[v][0] = cost + min(sumC[u][c] - p, 1LL * p);
pq.push({dp[v][0], v, 0});
}
if (dp[v][c] > cost) {
pq.push({dp[v][c] = cost, v, c});
}
}
} else {
for (auto it : g[u]) {
int c = it[0], v = it[1], p = it[2];
if (c != t) continue;
if (dp[v].count(0) == 0) dp[v][0] = 1e18;
if (dp[v][0] > cost + sumC[u][c] - p) {
dp[v][0] = cost + sumC[u][c];
pq.push({dp[v][0], v, 0});
}
}
}
}
if (dp[n].count(0) == 0) {
cout << - 1;
} else cout << dp[n][0];
return 0;
}
