#include <bits/stdc++.h> using namespace std; #define name "bus" #define MAXN 100005 #define pb push_back #define pf push_front #define ll long long #define bit(n,i) (((n)>>(i))&1) #define MASK(i) (1LL<<(i)) #define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for (int i=(a),_b=(b); i>=_b; i--) #define all(v) v.begin(),v.end() #define uni(v) v.erase(unique(all(v)),v.end()) #define ii pair<int, int> #define fs first #define sc second const ll ll_INF=1e18; const int INF=1e9; const int MOD=1e9+7; void add(int &u, int v){ u+=v; if (u>=MOD) u-=MOD; } void sub(int &u, int v){ u-=v; if (u<0) u+=MOD; } void maximize(int &u, int v){ u=max(u,v); } void minimize(int &u, int v){ u=min(u,v); } long long Rand(long long l, long long r){ ll ans=0; FOR(i,1,4){ ans=((ans<<15)^(((1<<15)-1)&rand())); } return l+ans%(r-l+1); } #define lli pair<ll, int> int n,m; int S,T,U,V; vector<ii> adj[MAXN]; ll d[4][MAXN]; priority_queue<lli,vector<lli>,greater<lli>> pq; void dijkstra(int type, int s){ FOR(i,1,n) d[type][i]=ll_INF; d[type][s]=0; pq.push({0,s}); while (pq.size()){ lli tmp=pq.top(); pq.pop(); ll cost=tmp.fs; int u=tmp.sc; if (cost>d[type][u]) continue; for (ii pairs:adj[u]){ int v=pairs.fs; ll w=pairs.sc; if (d[type][v]>d[type][u]+w){ d[type][v]=d[type][u]+w; pq.push((lli){d[type][v],v}); } } } } vector<int> g[MAXN],gd[MAXN]; ll dp[MAXN]; int in[MAXN],out[MAXN]; int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>n>>m>>S>>T>>U>>V; FOR(i,1,m){ int x,y,w; cin>>x>>y>>w; adj[x].pb({y,w}); adj[y].pb({x,w}); } dijkstra(0,S); dijkstra(1,T); dijkstra(2,U); dijkstra(3,V); ll dist=d[0][T]; FOR(i,1,n){ for (ii pairs:adj[i]){ int j=pairs.fs; ll w=pairs.sc; if (d[0][i]+d[1][j]+w==dist){ g[i].pb(j); gd[j].pb(i); ++out[i]; ++in[j]; } } } queue<int> Q; FOR(i,1,n){ dp[i]=d[2][i]; if (in[i]==0) Q.push(i); } ll res=ll_INF; while (Q.size()){ int u=Q.front(); Q.pop(); res=min(res,dp[u]+d[3][u]); for (int v:g[u]){ if (--in[v]==0) Q.push(v); dp[v]=min(dp[v],dp[u]); } } FOR(i,1,n){ dp[i]=d[2][i]; if (out[i]==0) Q.push(i); } while (Q.size()){ int u=Q.front(); Q.pop(); res=min(res,dp[u]+d[3][u]); for (int v:gd[u]){ if (--out[v]==0) Q.push(v); dp[v]=min(dp[v],dp[u]); } } cout<<res; return 0; }