#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
/**
* JOI 2020/2021 Final Round - Robot
* Karmaşıklık: O(M log M)
*/
typedef long long ll;
const ll INF = 1e18;
struct Edge {
int to, color;
ll cost;
};
struct State {
int u, color;
ll dist;
bool operator>(const State& other) const {
return dist > other.dist;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
vector<vector<Edge>> adj(N + 1);
vector<map<int, ll>> color_sum(N + 1); // Kavşaktaki renklerin toplam maliyeti
for (int i = 0; i < M; i++) {
int u, v, c;
ll p;
cin >> u >> v >> c >> p;
adj[u].push_back({v, c, p});
adj[v].push_back({u, c, p});
color_sum[u][c] += p;
color_sum[v][c] += p;
}
priority_queue<State, vector<State>, greater<State>> pq;
map<pair<int, int>, ll> dist_with_color; // (düğüm, renk) bazlı mesafeler
vector<ll> dist(N + 1, INF); // (sadece düğüm) bazlı mesafeler
// Başlangıç: Kavşak 1, maliyet 0. Renk 0 "normal" durumu temsil eder.
dist[1] = 0;
pq.push({1, 0, 0});
while (!pq.empty()) {
State curr = pq.top();
pq.pop();
int u = curr.u;
int c = curr.color;
ll d = curr.dist;
// Mevcut mesafe zaten daha iyiyse atla
if (c == 0) {
if (d > dist[u]) continue;
} else {
if (dist_with_color.count({u, c}) && d > dist_with_color[{u, c}]) continue;
}
for (auto& e : adj[u]) {
int v = e.to;
int nc = e.color;
ll np = e.cost;
if (c == 0) {
// Seçenek 1: Bu yolun rengini değiştir (Maliyet: np)
if (dist[v] > d + np) {
dist[v] = d + np;
pq.push({v, 0, dist[v]});
}
// Seçenek 2: Diğer aynı renkli yolların rengini değiştir (Maliyet: sum - np)
ll cost2 = color_sum[u][nc] - np;
if (dist[v] > d + cost2) {
dist[v] = d + cost2;
pq.push({v, 0, dist[v]});
}
// Seçenek 3: Bu yolu değiştirmeden geç (İleride diğerlerini değiştirmek üzere işaretle)
if (!dist_with_color.count({v, nc}) || dist_with_color[{v, nc}] > d) {
dist_with_color[{v, nc}] = d;
pq.push({v, nc, d});
}
} else {
// Daha önce bir 'nc' rengiyle geldik, bu yolun rengini değiştiremeyiz
// ancak bu renkteki diğer yolları değiştirebiliriz.
ll cost = color_sum[u][c] - np;
if (dist[v] > d + cost) {
dist[v] = d + cost;
pq.push({v, 0, dist[v]});
}
}
}
}
if (dist[N] == INF) cout << -1 << endl;
else cout << dist[N] << endl;
return 0;
}
