#include "bits/stdc++.h"
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m; cin >> n >> m;
vector adj(n + 1, map<int, vector<pair<int, long long>>>());
vector sum(n + 1, map<int, long long>());
for (int i = 0; i < m; i++) {
int a, b, c; cin >> a >> b >> c;
long long p; cin >> p;
adj[a][c].push_back({b, p});
adj[b][c].push_back({a, p});
sum[a][c] += p;
sum[b][c] += p;
}
using T = tuple<long long, int, int>;
priority_queue<T, vector<T>, greater<T>> pq;
vector dist(n + 1, map<int, long long>());
auto push = [&](int x, int c, long long d) -> void {
if (!dist[x].count(c) || d < dist[x][c])
pq.push({dist[x][c] = d, x, c});
};
push(1, 0, 0);
while (!pq.empty()) {
auto [d, x, c] = pq.top(); pq.pop();
if (dist[x][c] != d) continue;
if (c) {
for (auto [k, p] : adj[x][c])
push(k, 0, d + sum[x][c] - p);
} else {
for (auto [cc, _] : adj[x])
for (auto [k, p] : _) {
push(k, 0, d + p);
push(k, 0, d + sum[x][cc] - p);
push(k, cc, d);
}
}
}
if (dist[n].count(0))
cout << dist[n][0] << '\n';
else
cout << -1 << '\n';
return 0;
}
