#include <bits/stdc++.h> using namespace std; using ll = long long; struct Edge { int v, c; ll p; }; struct Node { int v, from, c; ll p; friend bool operator==(Node const& n1, Node const& n2) { return make_tuple(n1.v, n1.from, n1.c, n1.p) == make_tuple(n2.v, n2.from, n2.c, n2.p); } friend bool operator<(Node const& n1, Node const& n2) { return make_tuple(n1.v, n1.from, n1.c, n1.p) < make_tuple(n2.v, n2.from, n2.c, n2.p); } }; struct NodeHash { size_t operator()(Node const& n) const { size_t h = 0; h ^= std::hash<int>{}(n.v) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2); h ^= std::hash<int>{}(n.from) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2); h ^= std::hash<int>{}(n.c) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2); h ^= std::hash<long long>{}(n.p)+ 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2); return h; } }; vector<vector<Edge>> g; vector<unordered_map<int, int>> cnt; vector<unordered_map<int, ll>> cost; ll dijkstra() { priority_queue<pair<ll, Node>, vector<pair<ll, Node>>, greater<pair<ll, Node>>> pq; pq.push({0LL, {1, 0, 0, 0LL}}); unordered_map<Node, ll, NodeHash> dist; dist[{1, 0, 0, 0LL}] = 0LL; unordered_set<Node, NodeHash> processed; while (!pq.empty()) { auto[d, u] = pq.top(); pq.pop(); if (u.v == g.size()-1) return d; if (processed.count(u)) continue; processed.insert(u); for (auto e : g[u.v]) { if (e.v == u.from) continue; ll w = e.p; Node v = {e.v, u.v, e.c, e.p}; if (!dist.count(v) || dist[u] + w < dist[v]) { pq.push({dist[u] + w, v}); dist[v] = dist[u] + w; } } for (auto e : g[u.v]) { if (e.v == u.from) continue; ll w = cost[u.v][e.c] - e.p; if (u.c == e.c) w -= u.p; Node v = {e.v, u.v, 0, 0LL}; if (!dist.count(v) || dist[u] + w < dist[v]) { pq.push({dist[u] + w, v}); dist[v] = dist[u] + w; } } } return -1LL; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; g = vector<vector<Edge>>(n+1); cnt = vector<unordered_map<int, int>>(n+1); cost = vector<unordered_map<int, ll>>(n+1); for (int i = 0; i < m; i++) { int a, b, c; ll p; cin >> a >> b >> c >> p; g[a].push_back({b, c, p}); g[b].push_back({a, c, p}); cnt[a][c]++; cnt[b][c]++; cost[a][c] += p; cost[b][c] += p; } ll ans = dijkstra(); cout << ans; }