#include <bits/stdc++.h>
#include <experimental/random>
#include <random>
using namespace std;
using ll = long long;
using ld = long double;
const ll INF = 1e18, MOD = 1e9 + 7;
void solve();
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int q = 1;
//cin >> q;
while (q--) {
solve();
}
}
struct e {
ll v, c, d;
};
struct str {
ll u, c, d, f;
bool operator<(str a) const {
return u < a.u || (u == a.u && c < a.c) || (u == a.u && c == a.c && d < a.d) ||
(u == a.u && c == a.c && d == a.d && f < a.f);
}
};
void solve() {
ll n, m;
cin >> n >> m;
vector<vector<e>> g(n);
vector<unordered_map<ll, ll>> cnt(n);
for (int i = 0; i < m; i++) {
ll a, b, c, d;
cin >> a >> b >> c >> d;
a--, b--;
cnt[a][c] += d;
cnt[b][c] += d;
g[a].push_back({b, c, d});
g[b].push_back({a, c, d});
}
vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(m + 1, vector<ll>(2, INF)));
dp[0][0][0] = 0;
dp[0][0][1] = 0;
set<pair<ll, str>> dj;
dj.insert({0, {0, 0, 0, 0}});
while (!empty(dj)) {
ll w = dj.begin()->first;
ll u = dj.begin()->second.u;
ll dd = dj.begin()->second.d;
ll color = dj.begin()->second.c;
ll f = dj.begin()->second.f;
if (f) {
cnt[u][color] -= dd;
}
dj.erase(dj.begin());
for (auto [v, c, d]: g[u]) {
ll cost = w + d;
if (dp[v][c][1] > cost) {
dj.erase({dp[v][c][1], {v, c, d, 1}});
dp[v][c][1] = cost;
dj.insert({dp[v][c][1], {v, c, d, 1}});
}
cost = w + (cnt[u][c] - d);
if (dp[v][c][0] > cost) {
dj.erase({dp[v][c][0], {v, c, d, 0}});
dp[v][c][0] = cost;
dj.insert({dp[v][c][0], {v, c, d, 0}});
}
}
if (f) {
cnt[u][color] += dd;
}
}
ll ans = INF;
for (int i = 0; i <= m; i++) {
ans = min(ans, dp[n - 1][i][0]);
ans = min(ans, dp[n - 1][i][1]);
}
if (ans == INF) {
cout << -1;
} else {
cout << ans;
}
}
