#include <bits/stdc++.h>
using namespace std;
#define kien long long
#define pb push_back
#define FOR(i, a, b) for (int i = a;i <= b; i++)
#define pii pair<kien, kien>
const int MXN = 2e5 + 5;
const kien INF = (kien)4e18;
kien n, m, u, v;
kien d[MXN];
map<int, kien> pp[MXN];
map<int, kien> d2[MXN];
map<int, vector<pii>> dpc[MXN];
struct KBB {
kien mot, hai, ba;
};
struct day {
kien mot, hai, ba;
bool operator < (const day& x) const {
return mot > x.mot;
}
};
vector<KBB> dp[MXN];
void dijkstra (int s) {
priority_queue<day> q;
for (int i = 1; i <= n; ++i) d[i] = INF;
d[s] = 0;
q.push({d[s], s, 0});
while (!q.empty()) {
auto cur = q.top(); q.pop();
kien du = cur.mot;
int u = (int)cur.hai;
int pre = (int)cur.ba;
if (pre == 0) {
if (du > d[u]) continue;
} else {
if (!d2[u].count(pre) || du > d2[u][pre]) continue;
}
if (pre == 0) {
for (auto &e : dp[u]) {
int to = (int)e.mot;
int col = (int)e.hai;
kien w = e.ba;
if (d[to] > d[u] + (pp[u][col] - w)) {
d[to] = d[u] + (pp[u][col] - w);
q.push({d[to], to, 0});
}
if (d[to] > d[u] + w) {
d[to] = d[u] + w;
q.push({d[to], to, 0});
}
if (!d2[to].count(col) || d2[to][col] > d[u]) {
d2[to][col] = d[u];
q.push({d2[to][col], to, col});
}
}
} else {
for (auto &pr : dpc[u][pre]) {
int to = (int)pr.first;
kien w = pr.second;
if (d[to] > d2[u][pre] + pp[u][pre] - w) {
d[to] = d2[u][pre] + pp[u][pre] - w;
q.push({d[to], to, 0});
}
}
}
}
if (d[n] == INF) cout << -1 << '\n';
else cout << d[n] << '\n';
}
void solve() {
kien c, p;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
d[i] = INF;
dp[i].clear();
pp[i].clear();
d2[i].clear();
dpc[i].clear();
}
for (int i = 1; i <= m; ++i) {
cin >> u >> v >> c >> p;
dp[u].pb({v, c, p});
dp[v].pb({u, c, p});
dpc[u][c].pb({v, p});
dpc[v][c].pb({u, p});
pp[u][c] += p;
pp[v][c] += p;
}
dijkstra(1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
