#include <bits/stdc++.h>
using namespace std;
#define ar array
#define ll long long
const ll linf = 1e18;
#define int long long
void solve() {
int n, m;
cin >> n >> m;
vector<map<int, ll>> vc(n);
vector<vector<ar<int, 3>>> g(n);
for (int i = 0; i < m;i++) {
int u, v, c, w;
cin >> u >> v >> c >> w;
--u, --v;
g[u].push_back({v, c, w});
g[v].push_back({u, c, w});
vc[u][c] += w;
vc[v][c] += w;
}
priority_queue<ar<ll, 4>, vector<ar<ll, 4>>, greater<ar<ll, 4>> > pq;
vector<map<int, ll>> dp(n);
dp[0][0] = 0;
pq.push({0, 0, 0, 0});
while (!pq.empty()) {
auto [w, u, t, T] = pq.top();
pq.pop();
if (w != dp[u][t])
continue;
for (auto [v, c, w2] : g[u]) {
ll cur = vc[u][c] - w2;
if (t == c)
cur -= T;
if (dp[v].find(0) == dp[v].end())
dp[v][0] = linf;
if (cur + w < dp[v][0]) { // change everything but, current edge
dp[v][0] = cur + w;
pq.push({dp[v][0], v, 0, 0});
}
if (dp[v].find(c) == dp[v].end())
dp[v][c] = linf;
if (w2 + w < dp[v][c]) { // change current one
dp[v][c] = w2 + w;
pq.push({dp[v][c], v, c, w2});
}
}
}
ll ans = linf;
for (auto [_, x] : dp[n - 1])
ans = min(ans, x);
cout << (ans >= linf ? -1 : ans);
}
int32_t main() {
#ifdef Behruz
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}
