#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << endl)
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << " "); PRINT("}\n");)
typedef int64_t i64;
const i64 INF = i64(1e18); //1000000007; //998244353;
struct S {
int n, m;
vector<unordered_map<i64, set<pair<i64, i64>>>> edges;
vector<unordered_map<i64, i64>> csum;
void run() {
cin >> n >> m;
edges.resize(n);
csum.resize(n);
for (int i = 0; i < m; ++i) {
i64 a, b, c, p;
cin >> a >> b >> c >> p;
--a; --b;
edges[a][c].insert({b, p});
edges[b][c].insert({a, p});
csum[a][c] += p;
csum[b][c] += p;
}
int ii = 0;
for (auto node : edges) {
PV(ii++);
for (auto [id, s] : node) {
PV(id); PAR2(s);
}
}
vector<i64> d(n, INF);
vector<unordered_map<i64, i64>> d2(n);
d[0] = 0;
priority_queue<array<i64, 3>> q;
q.push({0, 0, 0});
while (!q.empty()) {
PAR(q.top());
i64 dist = -q.top()[0];
i64 node = q.top()[1];
i64 c = q.top()[2];
q.pop();
if (c) {
// you must only push "exclude the rest" into the queue
// d[node] = min(d[node], d2[node][c]);
if (d2[node][c] != dist) continue;
for (auto [next, wt] : edges[node][c]) {
i64 rest = d2[node][c] + csum[node][c] - wt;
if (rest < d[next]) {
d[next] = rest;
q.push({-rest, next, 0});
}
}
} else {
if (d[node] != dist) continue;
for (auto &[color, adj] : edges[node]) {
assert(color != 0);
for (auto [next, wt] : adj) {
assert(next >= 0 && next < n);
assert(csum[node].count(color));
i64 rest = d[node] + csum[node][color] - wt;
if (rest < d[next]) {
d[next] = rest;
q.push({-rest, next, 0});
}
if (d[node] + wt < d[next]) {
d[next] = d[node] + wt;
q.push({-d[node] - wt, next, 0});
}
if (!d2[next].count(color) || dist < d2[next][color]) {
d2[next][color] = dist;
q.push({-dist, next, color});
}
}
}
}
}
for (auto a : d2) {
PAR2(a);
}
PAR(d);
cout << (d[n - 1] >= INF ? -1 : d[n - 1]) << '\n';
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
auto sol = make_unique<S>();
sol->run();
}
