#include <bits/stdc++.h> using namespace std; using ll=long long; constexpr int MAXN=6e5+7; ll INF=1e18; vector<pair<int,ll>> graf[MAXN]; pair<pair<int,int>,ll> kraw[MAXN]; ll odl[MAXN]; ll odlA[MAXN]; ll odlB[MAXN]; bool odw[MAXN]; vector<pair<int,ll>> G[MAXN]; int n,m,A,B,C,D; void wczytanie(){ cin>>n>>m>>A>>B>>C>>D; int v,u;ll cena; for (int i=0;i<m;i++){ cin>>v>>u>>cena; graf[u].push_back({v,cena}); graf[v].push_back({u,cena}); kraw[i]={{u,v},cena}; } } void dijkstra_od_S(int S){ for (int i=1;i<=n;i++) odl[i]=INF; for (int i=1;i<=n;i++) odw[i]=0; odl[S]=0; priority_queue<pair<ll,int>> q; q.push({0,S}); int v; while (q.size()>0){ v=q.top().second;q.pop(); if (odw[v]) continue; odw[v]=1; for (pair<int,ll> u:graf[v]){ if (odl[u.first]>odl[v]+u.second){ odl[u.first]=odl[v]+u.second; q.push({-odl[u.first],u.first}); } } } } void stworz_G(){ int v,u;ll cena; ll OAB=odlA[B]; for (int i=0;i<m;i++){ v=kraw[i].first.first;u=kraw[i].first.second;cena=kraw[i].second; G[v].push_back({u,cena}); G[u].push_back({v,cena}); G[v+2*n].push_back({u+2*n,cena}); G[u+2*n].push_back({v+2*n,cena}); if (odlA[v]+cena+odlB[u]==OAB || odlB[v]+cena+odlA[u]==OAB){ G[v+n].push_back({u+n,0}); G[u+n].push_back({v+n,0}); } } for (int i=1;i<=n;i++){ G[i].push_back({i+n,0}); G[i+n].push_back({i+2*n,0}); } } ll solve(){ for (int i=1;i<=3*n;i++) odl[i]=INF; for (int i=1;i<=3*n;i++) odw[i]=0; odl[C]=0; priority_queue<pair<ll,int>> q; q.push({0,C}); int v; while (q.size()>0){ v=q.top().second;q.pop(); if (odw[v]) continue; odw[v]=1; for (pair<int,ll> u:G[v]){ if (odl[u.first]>odl[v]+u.second){ odl[u.first]=odl[v]+u.second; q.push({-odl[u.first],u.first}); } } } return min(odl[D],min(odl[D+n],odl[D+2*n])); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); wczytanie(); dijkstra_od_S(A); for (int i=1;i<=n;i++) odlA[i]=odl[i]; dijkstra_od_S(B); for (int i=1;i<=n;i++) odlB[i]=odl[i]; stworz_G(); cout<<solve(); }