#include <bits/stdc++.h> using namespace std; #define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define rall(s) s.rbegin(),s.rend() #define all(s) s.begin(),s.end() #define pb push_back #define fi first #define se second #define ll long long #define ld long double #define YES cout<<"YES\n" #define Yes cout<<"Yes\n" #define yes cout<<"yes\n" #define NO cout<<"NO\n" #define No cout<<"No\n" #define no cout<<"no\n" const int N = 1e5 + 9 , mod = 1e9 + 7; ll d[N] = {} , dp[N] = {} , a[N] = {}, b[N] , c[N]; struct edge{ int to , cost; }; set<int>vc[N]; vector<int>st1[N]; map<int,vector<edge>>v[N]; map<int,ll>sum[N] , d1[N]; void solve(){ ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn = 1e18 , mx = 0; cin>>n>>m; for(i = 1; i <= m; i++){ cin>>x>>y>>l>>r; vc[x].insert(l); vc[y].insert(l); v[x][l].pb({y , r}); v[y][l].pb({x , r}); sum[x][l] += r; sum[y][l] += r; } for(i = 1; i <= n; i++) d[i] = 1e18; set<pair<ll,pair<int,int>>>st; st.insert({0 , {0 , 1}}); d[1] = 0; for(i = 1; i <= n; i++) for(auto to : vc[i]) st1[i].pb(to); while(!st.empty()){ x = st.begin()->fi , y = st.begin()->se.se , k = st.begin()->se.fi; st.erase(st.begin()); if(k){ if(d1[y][k] != x) continue; for(auto to : v[y][k]){ z = x + sum[y][k] - to.cost; if(d[to.to] > z){ if(st.find({d[to.to] , {0 , to.to}}) != st.end()) st.erase({d[to.to] , {0 , to.to}}); d[to.to] = z , st.insert({d[to.to] , {0 , to.to }}); } } }else { if(d[y] != x) continue; for(auto it : st1[y]){ for(auto to : v[y][it]){ z = to.cost; if(z > sum[y][it] - to.cost) z = sum[y][it] - to.cost; z += x; if(d[to.to] > z){ if(st.find({d[to.to] , {0 , to.to}}) != st.end()) st.erase({d[to.to] , {0 , to.to}}); d[to.to] = z , st.insert({d[to.to] , {0 , to.to}}); } if(!d1[to.to].count(it) || x < d1[to.to][it]){ if(st.find({d1[to.to][it] , {it , to.to}}) != st.end()) st.erase({d1[to.to][it] , {it , to.to}}); d1[to.to][it] = x; st.insert({d1[to.to][it] , {it, to.to}}); } } } } } cout<<(d[n] >= 1e18 ? -1 : d[n])<<"\n"; } int main(){ TL; /* #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif */ int t = 1; //cin>>t; while(t--) { solve(); } } // Author : حسن

Main.cpp: In function 'void solve()':
Main.cpp:42:21: warning: narrowing conversion of 'y' from 'long long int' to 'int' [-Wnarrowing]
   42 |         v[x][l].pb({y , r});
      |                     ^
Main.cpp:42:25: warning: narrowing conversion of 'r' from 'long long int' to 'int' [-Wnarrowing]
   42 |         v[x][l].pb({y , r});
      |                         ^
Main.cpp:43:21: warning: narrowing conversion of 'x' from 'long long int' to 'int' [-Wnarrowing]
   43 |         v[y][l].pb({x , r});
      |                     ^
Main.cpp:43:25: warning: narrowing conversion of 'r' from 'long long int' to 'int' [-Wnarrowing]
   43 |         v[y][l].pb({x , r});
      |                         ^
Main.cpp:84:21: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   84 |                     if(st.find({d1[to.to][it] , {it , to.to}}) != st.end())
      |                     ^~
Main.cpp:86:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   86 |                         d1[to.to][it] = x;
      |                         ^~
Main.cpp:36:8: warning: unused variable 'q' [-Wunused-variable]
   36 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |        ^
Main.cpp:36:16: warning: unused variable 'j' [-Wunused-variable]
   36 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                ^
Main.cpp:36:29: warning: unused variable 's' [-Wunused-variable]
   36 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                             ^
Main.cpp:36:37: warning: unused variable 'f' [-Wunused-variable]
   36 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                     ^
Main.cpp:36:61: warning: unused variable 'mn' [-Wunused-variable]
   36 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                             ^~
Main.cpp:36:74: warning: unused variable 'mx' [-Wunused-variable]
   36 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                                          ^~