#include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define lll __ll128 #define sza(x) ((ll)x.size()) #define all(a) (a).begin(), (a).end() #define pb push_back #define pll pair<ll,ll> #ifdef DEBUG #include "helper.h" #else #define dbg(...) #endif #define log(a) 63-__builtin_clzll(a) const ll INF=1e18; const ll MOD=1e9+7; void solve() { int n,m; cin>>n>>m; vector<vector<tuple<int,int,ll>>> edges(n); vector<map<int,int>> colors(n); vector<map<int,ll>> dist(n); vector<map<int,ll>> sums(n); for(int i=0;i<n;i++){ dist[i][-1]=INF; } for(int i=0;i<m;i++){ int a,b,c,d; cin>>a>>b>>c>>d; a--,b--; edges[a].push_back({b,c,d}); edges[b].push_back({a,c,d}); colors[b][c]++; colors[a][c]++; sums[a][c]+=d; sums[b][c]+=d; dist[a][c]=INF; dist[b][c]=INF; } priority_queue<tuple<ll,int,int,ll,int> ,vector<tuple<ll,int,int,ll,int>>,greater<tuple<ll,int,int,ll,int>>> pq; pq.push({0,-1,0,0,-1}); dist[0][-1]=0; dbg(edges); while(!pq.empty()){ auto [cost,c,u,temp_cost,temp_u]=pq.top(); pq.pop(); if(dist[u][c]<cost)continue; // dbg(u,c); for(auto [nei,nei_c,nei_cost]:edges[u]){ if(nei==temp_u)continue; int color_num=colors[u][nei_c]; assert(color_num!=0); if(color_num==1){ if(dist[nei][-1]>cost){ dist[nei][-1]=cost; pq.push({cost,-1,nei,nei_cost,u}); } }else if (color_num==2 && nei_c==c){ if(dist[nei][-1]>cost){ dist[nei][-1]=cost; pq.push({cost,-1,nei,nei_cost,u}); } }else{ if(dist[nei][nei_c] > cost+nei_cost){ dist[nei][nei_c]=cost+nei_cost; pq.push({cost+nei_cost,nei_c,nei,nei_cost,u}); } ll extra=0; if(nei_c==c){ extra=temp_cost; } if(dist[nei][-1] > sums[u][nei_c]-nei_cost+cost-extra){ dist[nei][-1]=cost+sums[u][nei_c]-nei_cost+cost-extra; pq.push({cost+sums[u][nei_c]-nei_cost+cost-extra,-1,nei,nei_cost,u}); } } } } ll ans=INF; dbg(dist); for(auto i:dist[n-1]){ ans=min(ans,i.second); } if(ans==INF){ cout<<-1<<endl; }else{ cout<<ans<<endl; } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("boards.in","r",stdin); // freopen("boards.out","w",stdout); // cout<<1<<endl; // dbg(deals); // ll t; // cin>>t; // while(t--) solve(); }