#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2e5;
ll dp[MAXN + 1];
map<int, ll> ps[MAXN + 1], dp2[MAXN + 1];
map<int, vector<array<int, 3>>> adj[MAXN + 1];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int a, b, c, w;
cin >> a >> b >> c >> w;
adj[a][c].push_back({b, c, w});
adj[b][c].push_back({a, c, w});
ps[a][c] += w;
ps[b][c] += w;
}
for (int i = 1; i <= n; ++i) {
dp[i] = (ll)1e18;
}
priority_queue<array<ll, 3>> pq;
pq.push({0, 1, 0});
dp[1] = 0;
while (pq.size()) {
ll cost = -pq.top()[0];
int v = pq.top()[1];
int col = pq.top()[2];
pq.pop();
//~ cerr << v << " " << col << " = " << cost << "\n";
if (col) {
if (dp2[v][col] != cost) continue;
for (auto& [u, c, w] : adj[v][col]) {
ll cost1 = ps[v][c] - w + cost;
if (cost1 < dp[u]) {
dp[u] = cost1;
pq.push({-dp[u], u, 0});
}
}
} else {
if (dp[v] != cost) continue;
for (auto& E : adj[v]) {
for (auto& [u, c, w] : E.second) {
ll cost1 = ps[v][c] - w + cost;
if (cost1 < dp[u]) {
dp[u] = cost1;
pq.push({-dp[u], u, 0});
}
ll cost2 = w + cost;
if (cost2 < dp[u]) {
dp[u] = cost2;
pq.push({-dp[u], u, 0});
}
ll cost3 = cost;
if (!dp2[u].count(c) || cost3 < dp2[u][c]) {
dp2[u][c] = cost3;
pq.push({-dp2[u][c], u, c});
}
}
}
}
}
cout << (dp[n] == (ll)1e18 ? -1 : dp[n]) << "\n";
}
