#include <bits/stdc++.h> using namespace std; using ll = long long; struct Edge { int v, c; ll p; }; struct Node { int v, c; friend bool operator<(Node const& n1, Node const& n2) { return make_pair(n1.v, n1.c) < make_pair(n2.v, n2.c); } }; vector<vector<Edge>> g; vector<map<int, vector<Edge>>> g_c; vector<map<int, ll>> cost; ll dijkstra() { Node s = {1, 0}; priority_queue<pair<ll, Node>, vector<pair<ll, Node>>, greater<pair<ll, Node>>> pq; pq.push({0LL, s}); map<Node, ll> dist; dist[s] = 0LL; set<Node> processed; while (!pq.empty()) { auto[d, u] = pq.top(); pq.pop(); if (u.v == g.size()-1 && !u.c) return d; if (processed.count(u)) continue; processed.insert(u); if (u.c) { for (auto e : g_c[u.v][u.c]) { Node v = {e.v, 0}; ll w = cost[u.v][u.c] - e.p; if (!dist.count(v) || dist[u] + w < dist[v]) { pq.push({dist[u] + w, v}); dist[v] = dist[u] + w; } } } else { for (auto e : g[u.v]) { Node v = {e.v, 0}; ll w = min(e.p, cost[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]) { Node v = {e.v, e.c}; ll w = 0; if (!dist.count(v) || dist[u] + w < dist[v]) { pq.push({dist[u] + w, v}); dist[v] = dist[u] + w; } } } } return -1; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; g.resize(n+1); g_c.resize(n+1); cost.resize(n+1); for (int i = 0; i < m; i++) { int a, b, c; ll p; cin >> a >> b >> c >> p; cost[a][c] += p; cost[b][c] += p; g[a].push_back({b, c, p}); g[b].push_back({a, c, p}); g_c[a][c].push_back({b, c, p}); g_c[b][c].push_back({a, c, p}); } ll ans = dijkstra(); cout << ans; }