#include using namespace std; #define int ll #define fast_io cin.tie(0)->sync_with_stdio(0); #define endl '\n' typedef long long ll; int32_t main() { fast_io; int n, m; cin >> n >> m; using T = array; vector edges; vector>> g(n); for (int i = 0; i < m; i++) { int u, v, w, t; cin >> u >> v >> w >> t; --u, --v; edges.push_back({u, v, w, t}); g[u].push_back({v, w, i}); g[v].push_back({u, w, i}); } vector state(m); vector dist(n); vector> par(n); const int INF = 1e18; auto dijkstra = [&] (int s) { fill(dist.begin(), dist.end(), INF); dist[s] = 0; priority_queue, vector>, greater>> pq; pq.emplace(dist[s], s); while (pq.size()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto [v, w, i] : g[u]) { if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; par[v] = {u, i}; pq.emplace(dist[v], v); } } } }; dijkstra(0); int ans = dist[n - 1]; int at = n - 1; set> st; while (at != 0) { state[par[at].second]++; st.insert({par[at].first, at}); at = par[at].first; } for (int i = 0; i < n; i++) g[i].clear(); for (int i = 0; i < m; i++) { auto [u, v, w, t] = edges[i]; if (state[i]) { if (st.count({u, v})) { g[v].push_back({u, -w, i}); } else { g[u].push_back({v, -w, i}); } g[u].push_back({v, t, i}); g[v].push_back({u, t, i}); } else { g[u].push_back({v, w, i}); g[v].push_back({u, w, i}); } } fill(dist.begin(), dist.end(), INF); dist[0] = 0; deque dq; vector in(n); in[0] = true; dq.push_front(0); while (dq.size()) { int u = dq.front(); dq.pop_front(); in[u] = false; for (auto [v, w, _] : g[u]) { if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if (in[v]) continue; if (dq.size() && dist[dq.front()] < dist[v]) dq.push_back(v); else dq.push_front(v); in[v] = true; } } } ans += dist[n - 1]; cout << ans << endl; }