#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010, K = 4;
const ll inf = 1ll << 59;
unordered_map<int, vector<pair<int,int>>> edge[MAX_N];
int n, m;
ll dp[MAX_N], sec[MAX_N], fr[MAX_N], sef[MAX_N];
unordered_map<int, ll> mcdp[MAX_N];
struct info {
ll cur, len, col, lst, mc;
bool operator < (info b) const {
return len > b.len;
}
};
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int a, b, c, p, i = 0;i < m;++i) {
cin >> a >> b >> c >> p;
edge[a][c].pb(b, p);
edge[b][c].pb(a, p);
}
for (int i = 1;i <= n;++i) {
dp[i] = sec[i] = inf;
fr[i] = sef[i] = -1;
}
priority_queue<info> pq;
pq.push({1, 0, -1, -1, -1});
dp[1] = sec[1] = 0;
auto update = [&](int x, ll len, ll col, ll mc) {
if (mc == -1) {
bool ok = false;
if (len < dp[x]) {
swap(len, dp[x]);
swap(col, fr[x]);
ok = true;
}
if (len < sec[x] && fr[x] != col) {
swap(len, sec[x]);
swap(col, sef[x]);
ok = true;
}
return ok;
}
else {
if (!edge[x].count(mc)) return false;
if (mcdp[x].count(mc))
return chmin(mcdp[x][mc], len);
else return mcdp[x][mc] = len, true;
}
};
while (pq.size()) {
auto [x, len, col, lst, mc] = pq.top(); pq.pop();
DE(x, len, col);
if (mc == -1) {
if (len > sec[x]) continue;
for (auto [c, vec] : edge[x]) {
ll sum = 0;
for (auto [u, cost] : vec) {
if (u == lst && c != col) continue;
sum += cost;
}
for (auto [u, cost] : vec) {
if (u == lst) continue;
ll need = sum - cost;
if (c == col) need = inf;
if (update(u, need + len, c, -1))
pq.push({u, need + len, c, x, -1});
if (update(u, cost + len, -1, -1))
pq.push({u, cost + len, -1, x, -1});
if (update(u, len, -1, c))
pq.push({u, len, -1, x, c});
}
}
}
else {
if (len > mcdp[x][mc]) continue;
auto vec = edge[x][mc];
int c = mc;
ll sum = 0;
for (auto [u, cost] : vec)
sum += cost;
for (auto [u, cost] : vec) {
if (u == lst) continue;
ll need = sum - cost;
if (update(u, need + len, c, -1))
pq.push({u, need + len, c, x, -1});
}
}
}
if (dp[n] == inf) dp[n] = -1;
cout << dp[n] << '\n';
}
