#include <bits/stdc++.h>
#define int long long
#define data _data
using namespace std;
struct edge {
int to, c, p;
};
struct data {
int v, c, type, e;
};
bool operator<(edge a, edge b) {
if (a.to != b.to)
return a.to < b.to;
if (a.c != b.c)
return a.c < b.c;
return a.p < b.p;
}
const int N = 1e5 + 5, M = 2e5 + 5, inf = 1e18;
unordered_map<int, vector<pair<edge, int>>> g[N];
unordered_map<int, int> dp[N], psum[N];
unordered_map<int, data> pre[N];
int C[M];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
set<int> av;
for(int i = 1; i <= m; i++)
av.insert(i);
for (int i = 1; i <= m; i++) {
int u, v, c, p;
cin >> u >> v >> c >> p;
g[u][c].push_back({{v, c, p}, i});
g[v][c].push_back({{u, c, p}, i});
psum[u][c] += p;
psum[v][c] += p;
// C[i] = c;
// av.erase(c);
}
dp[1][0] = 0;
priority_queue<edge> pq;
pq.push({0, 1, 0});
while (pq.size()) {
auto [cost, v, c] = pq.top();
cost = -cost;
pq.pop();
if (c) {
if (dp[v][c] != cost) continue;
for (auto [i, num]: g[v][c]) {
int case0 = psum[v][c] - i.p + cost;
if (!dp[i.to].count(0) || case0 + cost < dp[i.to][0]) {
dp[i.to][0] = case0;
// pre[i.to][0] = {v, c, 0, num};
pq.push({-dp[i.to][0], i.to, 0});
}
}
} else {
if (dp[v][0] != cost) continue;
for (auto &i: g[v]) {
for (auto [j, num]: i.second) {
int case1 = psum[v][j.c] - j.p + cost;
if (!dp[j.to].count(0) || case1 < dp[j.to][0]) {
dp[j.to][0] = case1;
// pre[j.to][0] = {v, c, 1, num};
pq.push({-dp[j.to][0], j.to, 0});
}
int case2 = j.p + cost;
if (!dp[j.to].count(0) || case2 < dp[j.to][0]) {
dp[j.to][0] = case2;
// pre[j.to][0] = {v, c, 2, num};
pq.push({-dp[j.to][0], j.to, 0});
}
int case3 = cost;
if (!dp[j.to].count(j.c) || case3 < dp[j.to][j.c]) {
dp[j.to][j.c] = case3;
// pre[j.to][j.c] = {v, c, 3, num};
pq.push({-dp[j.to][j.c], j.to, j.c});
}
}
}
}
}
if (dp[n].count(0))
cout << dp[n][0];
else {
cout << -1;
return 0;
}
// cout << "\n";
// int v = n, c = 0;
// vector<int> way = {n};
// vector<int> e;
// while (make_pair(v, c) != make_pair(1LL, 0LL)) {
// auto [nv, nc, type, num] = pre[v][c];
// if (type <= 1) {
// for (auto [i, j]: g[nv][C[num]])
// if (j != num)
// e.push_back(j);
// } else if(type == 2) {
// e.push_back(num);
// }
// v = nv;
// c = nc;
// way.push_back(v);
// }
// reverse(way.begin(), way.end());
//// cout << way.size() << '\n';
// for(int i : way)2 * 2;
//// cout << i << " ";
//// cout << '\n' << e.size() << '\n';
// for(int i : e) {
//// cout << i << " " << *av.begin() << '\n';
// av.erase(av.begin());
// }
return 0;
}
