#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;
};
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]++;
cnt[b][c]++;
g[a].push_back({b, c, d});
g[b].push_back({a, c, d});
}
vector<vector<ll>> dp(n, vector<ll>(m + 2, INF));
dp[0][0] = 0;
set<pair<ll, pair<ll, ll>>> dj;
dj.insert({0, {0, 0}});
while (!empty(dj)) {
ll w = dj.begin()->first;
ll u = dj.begin()->second.first;
ll color = dj.begin()->second.second;
dj.erase(dj.begin());
cnt[u][color]--;
for (auto [v, c, d] : g[u]) {
ll cost = w;
ll sec = c;
if (cnt[u][c] != 1) {
cost += d;
sec = m + 1;
}
if (dp[v][sec] > cost) {
dj.erase({dp[v][sec], {v, sec}});
dp[v][sec] = cost;
dj.insert({dp[v][sec], {v, sec}});
}
}
cnt[u][color]++;
}
ll ans = INF;
for (int i = 0; i <= m + 1; i++) {
ans = min(ans, dp[n - 1][i]);
}
if (ans == INF) {
cout << -1;
} else {
cout << ans;
}
}
