#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
vector<map<ll, ll>> adj;
vector<ll> dp1;
vector<map<ll, ll>> dp2;
int main() {
ll n,m; cin >> n >> m;
adj.resize(n+1);
vector<vector<pair<int, P>>> ajd(n+1);
dp1.resize(n+1, 1e9);
dp2.resize(n+1);
for (int i = 0; i < m; i++) {
ll a, b, c, p; cin >> a >> b >> c >> p;
adj[a][c] += p;
adj[b][c] += p;
ajd[a].push_back({b, {c, p}}); // leading node, color, cost: <node, <color, cost>>
ajd[b].push_back({a, {c, p}});
}
vector<vector<pair<int, P>>> AJD = ajd;
/*
for (int i = 1; i <= n; i++) {
for (auto u1: ajd[i]) {
cout << "u: " << u1.f << ", " << u1.s.f << ", " << u1.s.s << "\n";
}
cout << "\n";
}
cout << "\n";
cout << "\n";
cout << "\n";
cout << "\n";
*/
for (int i = 1; i <= n; i++) {
for (auto &u: ajd[i]) {
//if (u.s.s != adj[i][u.s.f]) u.s.s = min(adj[i][u.s.f]-u.s.s, u.s.s);
u.s.s = min(adj[i][u.s.f]-u.s.s, u.s.s);
}
}
/*
for (int i = 1; i <= n; i++) {
for (auto u1: ajd[i]) {
cout << "u: " << u1.f << ", " << u1.s.f << ", " << u1.s.s << "\n";
}
cout << "\n";
}
*/
priority_queue<P, vector<P>, greater<P>> pq;
ll start = 1;
dp1[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
P u = pq.top(); pq.pop();
if (u.f != dp1[u.s]) continue;
//cout << "u(val, node): " << u.f << ", " << u.s << "\n";
ll counter = 0;
for (pair<int, P> u1: ajd[u.s]) {
//cout << "u1(nxtnode, color, cost): " << u1.f << ", " << u1.s.f << ", " << u1.s.s << '\n';
if (dp2[u1.f].count(u1.s.f) > 0) {
//cout << "dp2 of u1.f, u1.s.f MAY BECOME dp1 of u.s: " << u1.f << ", " << u1.s.f << " ::: " << u.s << "\n";
//cout << "dp2[u1.f][u1.s.f], dp1[u.s]: " << dp2[u1.f][u1.s.f] << ", " << dp1[u.s] << '\n';
dp2[u1.f][u1.s.f] = min(dp2[u1.f][u1.s.f], dp1[u.s]);
} else {
//cout << "dp2 of u1.f, u1.s.f becomes dp1 of u.s: " << u1.f << ", " << u1.s.f << " ::: " << u.s << "\n";
//cout << "dp1[u.s]: " << dp1[u.s] << '\n';
dp2[u1.f][u1.s.f] = dp1[u.s];
}
if (u1.s.s != AJD[u.s][counter].s.s) {
ll v1 = dp1[u.s]+u1.s.s;
bool truzz = dp2[u.s].count(u1.s.f)>0;
if (truzz) {
ll v2 = dp2[u.s][u1.s.f]+u1.s.s;
if (v1 < dp1[u1.f] || v2 < dp1[u1.f]) {
//cout << "u, dp1[u.s], u1.s.s: " << u.s << ", " << dp1[u.s] << "\n";
//cout << "yo wtf here are u1.f, v1, v2: " << u1.f << ", " << v1 << ", " << v2 << "\n";
pq.push({dp1[u1.f]=min(v1, v2), u1.f});
}
} else {
if (v1 < dp1[u1.f]) {
pq.push({dp1[u1.f]=v1, u1.f});
}
}
} else {
if (dp1[u.s] + u1.s.s < dp1[u1.f]) {
//cout << "YO, u1.f, u.s, dp1[u.s], u1.s.s: " << u1.f << ", " << u.s << ", " << dp1[u.s] << ", " << u1.s.s << '\n';
dp1[u1.f] = dp1[u.s]+u1.s.s;
pq.push({dp1[u1.f], u1.f});
}
}
counter++;
}
}
if (dp1[n] != 1e9) {
cout << dp1[n];
} else {
cout << -1;
}
}
