#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 = 100000+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<ll> dijkstra(ll i){ vector<ll> dist(n,-1); priority_queue<pair<ll,ll>> cola; cola.push({0,i}); while(!cola.empty()){ ll nd=cola.top().snd; ll c=cola.top().fst*-1; cola.pop(); //cout<<nd<<" "<<c<<'\n'; if(dist[nd]!=-1) continue; dist[nd]=c; for(auto i:adj[nd]) if(dist[i.fst.fst]==-1){ cola.push({(c+ari[i.snd].snd)*-1,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}); } vector<ll> distS = dijkstra(s); vector<ll> distT = dijkstra(t); ll rdist = distS[t]; //cout<<rdist<<'\n'; forn(i,0,m){ if(distS[ari[2*i].fst.fst]+distT[ari[2*i].fst.snd]+ari[2*i].snd==rdist){ ari[2*i].snd=0; } if(distS[ari[2*i+1].fst.fst]+distT[ari[2*i+1].fst.snd]+ari[2*i+1].snd==rdist){ ari[2*i+1].snd=0; } } vector<ll> distU = dijkstra(u); vector<ll> distV = dijkstra(v); ll res = 10000000000000000; if(distU[v]!=-1) res=min(res,distU[v]); if(distV[u]!=-1) res=min(res,distV[u]); cout<<res<<'\n'; return 0; }