#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); } 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() { vector<Node> nodes = {{1, 0, false, 0, 0LL}}; priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.push({0LL, 0}); vector<vector<unordered_map<int, ll>>> dist(2, vector<unordered_map<int, ll>>(g.size())); dist[0][1][0] = 0LL; vector<vector<unordered_set<int>>> processed(2, vector<unordered_set<int>>(g.size())); while (!pq.empty()) { auto[d, idx] = pq.top(); pq.pop(); Node u = nodes[idx]; if (u.v == g.size()-1) return d; if (dist[u.changed][u.v][u.from] != d) continue; processed[u.changed][u.v].insert(u.from); 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[v.changed][v.v].count(v.from) || dist[u.changed][u.v][u.from] + w < dist[v.changed][v.v][v.from]) { pq.push({dist[u.changed][u.v][u.from] + w, nodes.size()}); nodes.push_back(v); dist[v.changed][v.v][v.from] = dist[u.changed][u.v][u.from] + 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[v.changed][v.v].count(v.from) || dist[u.changed][u.v][u.from] + w < dist[v.changed][v.v][v.from]) { pq.push({dist[u.changed][u.v][u.from] + w, nodes.size()}); nodes.push_back(v); dist[v.changed][v.v][v.from] = dist[u.changed][u.v][u.from] + 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; }