#include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++) #define FORNG(i,r,l) for(int i = (r), _l = (l); i >= _l; i--) #define REP(i,r) for(int i = 0, _r = (r); i < _r; i++) #define endl '\n' #define fi first #define se second #define pb push_back #define size(v) ((ll)(v).size()) #define all(v) (v).begin(),(v).end() #define MASK(x) (1LL << (x)) #define BIT(x,i) (((x) >> (i)) & 1) const ll MOD = 1e9 + 7, N = 2e5 + 36, LOG = 18; const ll INF = 1e18 + 20; int n,m,s,t,p,q; vector<pair<int,int>> adj[N]; ll d1[N],d2[N],dd[N],dp[N][2]; ll ans = INF; void dijk(int st,ll d[]){ FOR(i,1,n)d[i] = INF; priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> qu; qu.push({0, st}); d[st] = 0; while(!qu.empty()){ ll dist = qu.top().fi; int u = qu.top().se; qu.pop(); if(dist > d[u])continue; for(auto &[v, w] : adj[u]){ if(dist + w < d[v]){ d[v] = dist + w; qu.push({d[v], v}); } } } } void dijk2(int st,int ed){ FOR(i,1,n)dp[i][0] = dp[i][1] = dd[i] = INF; priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> qu; dp[st][0] = d1[st]; dp[st][1] = d2[st]; qu.push({0, st}); while(!qu.empty()){ ll dist = qu.top().fi; int u = qu.top().se; qu.pop(); if(dist > dd[u])continue; for(auto &[v, w] : adj[u]){ if(dist + w == dd[v]){ dp[v][0] = min(dp[u][0], d1[v]); dp[v][1] = min(dp[u][1], d2[v]); } if(dist + w < dd[v]){ dd[v] = dist + w; dp[v][0] = min(dp[u][0], d1[v]); dp[v][1] = min(dp[u][1], d2[v]); qu.push({dd[v], v}); } } } ans = min(ans, dp[ed][0] + dp[ed][1]); } int main(){ //freopen(".INP", "r", stdin); //freopen(".OUT", "w", stdout); ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>m; cin>>s>>t; cin>>p>>q; FOR(i,1,m){ int u,v,w;cin>>u>>v>>w; adj[u].pb({v, w}); adj[v].pb({u, w}); } dijk(p, d1); dijk(q, d2); ans = d1[q]; dijk2(s, t); dijk2(t, s); cout<<ans; }