//#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”) struct road{ int dest, color, cost; }; int INF = 1e18; int n, m; vector<map<int, int>>col_freqs; vector<vector<road>>adj; map<pii, int>gethash; vector<pii>getpair(50001); void disjkstra(){ vector<int>dist(50001, 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, col_used] = getpair[pq.top().second]; pq.pop(); if(dist[h] > d){ continue; } //visit neighbors for(auto [b, col, price] : adj[node]){ int colfreq = col_freqs[node][col]; if(col == col_used){ //cout << d << " " << node << endl; colfreq--; } if(colfreq <= 1){ //cost is nothing int newhash = gethash[{b, 0}]; if(d < dist[newhash]){ //push it dist[newhash] = d; pq.push({d, newhash}); } } else{ //cost is the price int newhash = gethash[{b, col}]; if(d + price < dist[newhash]){ dist[newhash] = d + price; pq.push({d + price, newhash}); } } } } //find the in of the dist[gethash[{n-1,x}]], where x can be anything int ans = INF; for(auto [b, col, price] : adj[n - 1]){ ans = min(ans, dist[gethash[{n - 1, col}]]); } 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<road>>(n); col_freqs = vector<map<int, int>>(n); int ind = 0; for(int i = 0; i < m; ++i){ int a, b, col, cost; cin >> a >> b >> col >> cost; --a; --b; adj[a].push_back({b, col, cost}); adj[b].push_back({a, col, cost}); col_freqs[a][col]++; col_freqs[b][col]++; if(!gethash.count((pii){ a, col })){ gethash[(pii){ a, col }] = ind; getpair[ind] = (pii){a, col}; ind++; } if(!gethash.count((pii){ b, col })){ gethash[(pii){ b, col }] = ind; getpair[ind] = (pii){b, col}; ind++; } } for(int i = 0; i < n; ++i){ gethash[{i, 0}] = ind; getpair[ind] = {i, 0}; ind++; } disjkstra(); }