#include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define lll __ll128 #define sza(x) ((ll)x.size()) #define all(a) (a).begin(), (a).end() #define pb push_back #define pll pair<ll,ll> #ifdef DEBUG #include "helper.h" #else #define dbg(...) #endif #define log(a) 63-__builtin_clzll(a) const ll INF=1e18; const ll MOD=1e9+7; struct Fenwick { int n; vector<ll> bit; Fenwick() : n(0) {} Fenwick(int n_) { init(n_); } void init(int n_) { n = n_; bit.assign(n+1, 0); } // add value v at 1-based index idx void add1(int idx, ll v) { for (; idx <= n; idx += idx & -idx) bit[idx] += v; } // sum over [1..idx] where idx is 1-based ll sum1(int idx) const { ll s = 0; for (; idx > 0; idx -= idx & -idx) s += bit[idx]; return s; } ll sumq(int idx1,int idx2){ if(idx1==1)return sum1(idx2); return sum1(idx2)-sum1(idx1-1); } }; void solve() { int n,m,s,t,u,v; cin>>n>>m; cin>>s>>t>>u>>v; s--,u--,v--,t--; vector<vector<pair<int,ll>>> edges(n); for(int i=0;i<m;i++){ int a,b; ll c; cin>>a>>b>>c; a--,b--; edges[a].push_back({b,c}); edges[b].push_back({a,c}); } auto dik1=[&](int s){ vector<vector<int>> par(n); vector<ll> dist(n,INF); dist[s]=0; priority_queue<pair<ll,int>> pq; pq.push({0,s}); while(!pq.empty()){ auto [c,u]=pq.top(); pq.pop(); if(dist[u]<c)continue; for(auto [v,w]:edges[u]){ if(dist[v]>w+dist[u]){ par[v].clear(); par[v].push_back(u); dist[v]=w+dist[u]; pq.push({dist[v],v}); }else if(dist[v]==w+dist[u]){ par[v].push_back(u); } } } return make_pair(dist,par); }; auto dik2=[&](int s){ vector<ll> dist(n,INF); dist[s]=0; priority_queue<pair<ll,int>> pq; pq.push({0,s}); while(!pq.empty()){ auto [c,u]=pq.top(); pq.pop(); if(dist[u]<c)continue; for(auto [v,w]:edges[u]){ if(dist[v]>w+dist[u]){ dist[v]=w+dist[u]; pq.push({dist[v],v}); }else if(dist[v]==w+dist[u]){ } } } return dist; }; auto [dists,par]=dik1(s); auto distu=dik2(u); auto distv=dik2(v); dbg(distv); vector<set<int>> new_edges(n); auto dfs1=[&](auto && dfs1,int vertex) -> void { for(auto nei:par[vertex]){ new_edges[nei].insert(vertex); dfs1(dfs1,nei); } }; dfs1(dfs1,t); dbg(new_edges); vector<ll> dpv(n,INF); vector<ll> dpu(n,INF); vector<int> inb(n); for(auto i:new_edges){ for(auto ii:i){ inb[ii]++; } } ll ans=INF; auto dfs=[&](auto && dfs,int vertex,ll u_dis,ll v_dis) -> void { u_dis=min(u_dis,distu[vertex]); v_dis=min(v_dis,distv[vertex]); ans=min(ans,u_dis+v_dis); for(auto nei:new_edges[vertex]){ dfs(dfs,nei,u_dis,v_dis); } }; dfs(dfs,s,INF,INF); dbg(dpu,dpv); cout<<min(ans,distv[u])<<endl; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("boards.in","r",stdin); // freopen("boards.out","w",stdout); // cout<<1<<endl; // dbg(deals); // ll t; // cin>>t; // while(t--) solve(); }