#ifndef DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,abm,mmx,fma,popcnt")
#endif
#include <bits/stdc++.h>
#define int long long
using ll = long long;
using namespace std;
const int INF = 1e18;
int n, m;
vector<vector<array<int, 3>>> adj;
vector<map<int, int>> cost_sum;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
adj.assign(n, {});
cost_sum.assign(n, {});
for (int i=0; i<m; i++) {
int a, b, c, p;
cin >> a >> b >> c >> p;
a--; b--;
adj[a].push_back({b, c, p});
adj[b].push_back({a, c, p});
cost_sum[a][c] += p;
cost_sum[b][c] += p;
}
priority_queue<pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>> pq;
vector<int> dist(n, INF);
vector<map<int, int>> min_cost_col(n);
pq.push({0, 0});
while (!pq.empty()) {
auto [d, v] = pq.top(); pq.pop();
if (dist[v] < INF) continue;
dist[v] = d;
for (auto [u, c, p] : adj[v]) {
if (dist[u] < INF) continue;
if (cost_sum[v][c] == p) {
// only one edge of color c
pq.push({d, u});
} else {
pq.push({d+p, u});
if (min_cost_col[u].count(c) == 0) min_cost_col[u][c] = INF;
min_cost_col[u][c] = min(min_cost_col[u][c], d);
pq.push({d + cost_sum[v][c]-p, u});
// Case 2
if (min_cost_col[v].count(c) == 0) min_cost_col[v][c] = INF;
pq.push({min_cost_col[v][c]+cost_sum[v][c]-p, u});
}
}
}
if (dist[n-1] >= INF) {
cout << -1 << "\n";
return 0;
}
cout << dist[n-1] << "\n";
}
