#include <bits/stdc++.h>
using namespace std;
using lint = long long;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
vector<map<int, lint>> S(N);
vector<map<int, vector<pair<int, int>>>> adj(N);
for (int i = 0; i < M; i++) {
int u, v, c, w;
cin >> u >> v >> c >> w;
u--, v--;
S[u][c] += w;
S[v][c] += w;
adj[u][c].push_back({v, w});
adj[v][c].push_back({u, w});
}
// Options when traversing an edge:
// - Change the next road
// - Costs P[e]
// - Change other adjacent road, last road unchanged or has different color
// - Costs S[u][C[e]] - P[e]
// - Change other adjacent road, last road changed and has same color
// - Costs S[u][C[e]] - P[e] - P[last]
//
// dist[u][0] = minimum cost to vertex u, no restrictions
// dist[u][c] = minimum cost to vertex u, where the next road must be of color c (use option 3 next)
vector<map<int, lint>> dist(N);
priority_queue<array<lint, 3>, vector<array<lint, 3>>, greater<array<lint, 3>>> pq;
const auto Relax = [&](int u, int c, lint d) {
if (dist[u].count(c) == 0 || dist[u][c] > d) {
dist[u][c] = d;
pq.push({d, u, c});
}
};
Relax(0, 0, 0);
while (!pq.empty()) {
lint d = pq.top()[0];
int u = (int) pq.top()[1];
int c = (int) pq.top()[2];
pq.pop();
if (dist[u][c] != d) {
continue;
}
if (c == 0) {
for (const auto &adjc : adj[u]) {
for (const auto &[v, w] : adjc.second) {
Relax(v, 0, d + w); // Option 1
Relax(v, 0, d + S[u][adjc.first] - w); // Option 2
Relax(v, adjc.first, d); // Option 3, Part 1
}
}
} else {
for (const auto &[v, w] : adj[u][c]) {
Relax(v, 0, d + S[u][c] - w); // Option 3, Part 2
}
}
}
cout << (dist[N - 1].count(0) ? dist[N - 1][0] : -1) << '\n';
return 0;
}
