#include <bits/stdc++.h> #define fst first #define snd second #define pb push_back #define SZ(x) (int)x.size() #define ALL(x) x.begin(),x.end() #define mset(a,v) memset(a,v,sizeof(a)) #define forn(i,a,b) for(int i = a; i < b; i++) #define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) using namespace std; typedef long long ll; const int MAXM = 400000+5; const int MAXN = 500000+5; ll n,m; ll s,t; ll u,v; pair<pair<ll,ll>,ll> ari[MAXM*2]; vector<pair<pair<ll,ll>,ll>> adj[MAXN]; vector<vector<ll>> dijkstra(ll i){ vector<vector<ll>> dist(n,vector<ll>(2,-1)); priority_queue<pair<pair<ll,ll>,pair<ll,ll>>> cola; cola.push({{0,0},{-1,i}}); while(!cola.empty()){ ll nd=cola.top().snd.snd; ll c=cola.top().fst.fst*-1; ll state = cola.top().fst.snd*-1; ll iari = cola.top().snd.fst; cola.pop(); //cout<<nd<<" "<<c<<'\n'; if(dist[nd][state]!=-1) continue; dist[nd][state]=c; for(auto i:adj[nd]){ if(ari[i.snd].snd==0 && state!=0){ ll nstate = state; ll niari = i.snd; cola.push({{(c+i.fst.snd)*-1,-1},{niari,i.fst.fst}}); continue; } ll nstate = state; ll niari = i.snd; if(ari[i.snd].snd!=0 && iari!=-1 && ari[iari].snd==0) nstate=1; cola.push({{(c+ari[i.snd].snd)*-1,nstate*-1},{niari,i.fst.fst}}); } } return dist; } int main(){FIN; cin>>n>>m; cin>>s>>t; s--; t--; cin>>u>>v; u--; v--; forn(i,0,m){ cin>>ari[2*i].fst.fst; ari[2*i].fst.fst--; cin>>ari[2*i].fst.snd; ari[2*i].fst.snd--; cin>>ari[2*i].snd; ari[2*i+1].fst.fst = ari[2*i].fst.snd; ari[2*i+1].fst.snd = ari[2*i].fst.fst; ari[2*i+1].snd=ari[2*i].snd; } forn(i,0,m){ ll uu = ari[2*i].fst.fst; ll vv = ari[2*i].fst.snd; ll c = ari[2*i].snd; adj[uu].pb({{vv,c},2*i}); adj[vv].pb({{uu,c},2*i+1}); } //cout<<"todo acomodado\n"; vector<vector<ll>> distS = dijkstra(s); vector<vector<ll>> distT = dijkstra(t); ll rdist = distS[t][0]; // cout<<"primeros dijkstra listos\n"; //cout<<rdist<<'\n'; forn(i,0,m){ /* cout<<i<<" "<<2*i<<" "<<2*i+1<<"------------------------------"<<'\n'; cout<<ari[2*i].fst.fst<<" "<<ari[2*i].fst.snd<<" "<<distS[ari[2*i].fst.fst][0] + distT[ari[2*i].fst.snd][0] + ari[2*i].snd<<'\n'; cout<<ari[2*i+1].fst.fst<<" "<<ari[2*i+1].fst.snd<<" "<<distS[ari[2*i+1].fst.fst][0] + distT[ari[2*i+1].fst.snd][0] + ari[2*i+1].snd<<'\n';*/ if(distS[ari[2*i].fst.fst][0] + distT[ari[2*i].fst.snd][0] + ari[2*i].snd == rdist){ ari[2*i].snd=0; } if(distS[ari[2*i+1].fst.fst][0] + distT[ari[2*i+1].fst.snd][0] + ari[2*i+1].snd == rdist){ ari[2*i+1].snd=0; } } //cout<<"aristas listas\n"; vector<vector<ll>> distU = dijkstra(u); vector<vector<ll>> distV = dijkstra(v); ll res = 10000000000000000; if(distU[v][0]!=-1) res=min(res,distU[v][0]); if(distU[v][1]!=-1) res=min(res,distU[v][1]); if(distV[u][0]!=-1) res=min(res,distV[u][0]); if(distV[u][1]!=-1) res=min(res,distV[u][1]); cout<<res<<'\n'; return 0; }