#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5+1; const int MAXM = 2e5+1; const long long inf = 1e18; int N,M,S,T,U,V; vector<pair<long long, long long>> G[MAXN]; vector<long long> distuv[2],distst[2],bestu[2],bestv[2]; vector<long long> dijkstra(int start){ vector<long long> dist(N+1,inf); dist[start]=0; priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq; pq.push({dist[start],start}); while(!pq.empty()){ auto p = pq.top(); pq.pop(); long long d = p.first, v = p.second; if(d!=dist[v]) continue; for(auto e: G[v]){ long long u=e.first,w=e.second; if(d+w<dist[u]){ dist[u]=d+w; pq.push({dist[u],u}); } } } return dist; } vector<long long> dijkstra2(int start, int whichst, int whichuv){ vector<long long> best(N+1,inf); priority_queue<array<long long, 3>, vector<array<long long, 3>>, greater<array<long long, 3>>> pq; pq.push({0,start,distuv[whichuv][start]}); while(!pq.empty()){ auto p = pq.top(); pq.pop(); long long d = p[0], v = p[1], bestuv = p[2]; if(d+distst[whichst^1][v]!=distst[0][T]) continue; if(bestuv>=best[v]) continue; best[v]=bestuv; for(auto e: G[v]){ long long u=e.first,w=e.second; long long newdist = d+w; if(newdist + distst[whichst^1][u]!=distst[0][T]) continue; long long nb = min(bestuv,distuv[whichuv][u]); pq.push({newdist,u,nb}); } } return best; } void solve(){ cin >> N >> M >> S >> T >> U >> V; for(int i=0; i<M; i++){ long long a,b,w; cin >> a >> b >> w; G[a].push_back({b,w}); G[b].push_back({a,w}); } distst[0] = dijkstra(S); distst[1] = dijkstra(T); distuv[0] = dijkstra(U); distuv[1] = dijkstra(V); bestu[0]=dijkstra2(S,0,0); bestu[1]=dijkstra2(T,1,0); bestv[0]=dijkstra2(S,0,1); bestv[1]=dijkstra2(T,1,1); long long ans = distuv[0][V]; for(int i=1; i<=N; i++){ long long b1 = distuv[0][i]+min(bestv[0][i],bestv[1][i]); long long b2 = distuv[1][i]+min(bestu[0][i],bestu[1][i]); //cout << i << " " << b1 << " " << b2 << "xd\n"; ans=min(ans,min(b1,b2)); } cout << ans << "\n"; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int t=1; //cin>>t; while(t--) solve(); }