#include <bits/stdc++.h> using namespace std; using ll = long long; struct Edge { int v; int c; ll p; friend bool operator<(Edge const& e1, Edge const& e2) { return make_tuple(e1.v, e1.c, e1.p) < make_tuple(e2.v, e2.c, e2.p); } }; struct Node { int v; int from; bool changed; int c; ll p; friend bool operator<(Node const& n1, Node const& n2) { return make_tuple(n1.v, n1.from, n1.changed) < make_tuple(n2.v, n2.from, n2.changed); } }; 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}}); map<Node, ll> dist; dist[{1, 0, false, 0, 0LL}] = 0LL; set<Node> 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, true, 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, false, 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; }