//#pragma GCC optimize ("O3") #include<iostream> #include<vector> #include<set> #include<map> #include<iomanip> #include <cassert> #include<algorithm> #include <cstring> #include<unordered_set> #include<queue> #include <array> #include<cmath> #include<unordered_map> #include<queue> #include <list> #include <bitset> using namespace std; #define int long long #define pii pair<int,int> #define LL long long #pragma GCC optimize("O3,unroll-loops") #pragma GCC target ("avx2,bmi,bmi2,lzcnt,popcnt") int INF = 1e18; int n, m; vector<map<int, int>>col_prices; vector<vector<int>>adj; map<pii, int>gethash; vector<pii>getpair(600001); vector<pair<pii, pii>>edges; void disjkstra(){ vector<int>dist(600001, INF); dist[gethash[{0, 0}]] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq; pq.push({0, gethash[{0, 0}]}); while(!pq.empty()){ int d = pq.top().first; int h = pq.top().second; auto [node, edge_used] = getpair[pq.top().second]; pq.pop(); if(dist[h] > d){ continue; } //visit neighbors for(auto e : adj[node]){ auto [nodes, info] = edges[e]; auto [a, b] = nodes; int dest = a == node ? b : a; auto [col, p] = info; int totcost = col_prices[node][col]; int everything_cost = col_prices[node][col] - p; int paintyou_cost = p; if(col == edges[edge_used].second.first){ //this means that the cost of painting everything is -edge[edges_used].second.second //paint cost is either painting everything except for it or just painting it everything_cost -= edges[edge_used].second.second; } int hash1 = gethash[{dest, e}]; int hash2 = gethash[{dest, 0}]; if(d + p < dist[hash1]){ dist[hash1] = d + p; pq.push({d + p, hash1}); } if(d + everything_cost < dist[hash2]){ dist[hash2] = d + everything_cost; pq.push({d + everything_cost, hash2}); } } } //find the in of the dist[gethash[{n-1,x}]], where x can be anything int ans = INF; for(int e : adj[n - 1]){ ans = min(ans, dist[gethash[{n - 1, e}]]); } ans = min(ans, dist[gethash[{n - 1, 0}]]); if(ans == INF){ cout << "-1"; } else{ cout << ans; } } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; adj = vector<vector<int>>(n); col_prices = vector<map<int, int>>(n); edges = vector<pair<pii, pii>>(m + 1); int ind = 0; for(int i = 1; i <= m; ++i){ int a, b, col, cost; cin >> a >> b >> col >> cost; --a; --b; adj[a].push_back(i); adj[b].push_back(i); edges[i] = {{a, b}, {col, cost}}; col_prices[a][col] += cost; col_prices[b][col] += cost; if(!gethash.count((pii){ a, i })){ gethash[(pii){ a, i }] = ind; getpair[ind] = (pii){a, i}; ind++; } if(!gethash.count((pii){ b, i })){ gethash[(pii){ b, i }] = ind; getpair[ind] = (pii){b, i}; ind++; } } for(int i = 0; i < n; ++i){ gethash[(pii){ i, 0 }] = ind; getpair[ind] = (pii){i, 0}; ind++; } //return 0; disjkstra(); }