#include <bits/stdc++.h> using namespace std; #define ll long long #define fr(i,a,b,c) for(ll i = a;i<b;i+=c) #define fre(i,a,b,c) for(int i = a;i>=b;i-=c) #define fs first #define sc second #define all(a) a.begin(),a.end() #define IINF 2000000005 #define LINF 1000000000000000005 #define str string #define endl '\n' using pii = pair<int,int>; using pll = pair<ll,ll>; using tiii = tuple<ll,int,int>; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); } ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); } constexpr int MOD = 1000000007; //998244353 int n,m,s1,e1,s2,e2; vector<pii> a[100005]; ll dist1[100005],dist2[100005],dist3[100005],dp1[100005],dp2[100005]; bool vis[100005]; void djs(int s,ll dist[]){ fill(dist,dist + n + 1,LINF); priority_queue<pll,vector<pll>,greater<pll>> pq; dist[s] = 0; pq.push({0,s}); while(!pq.empty()){ auto [d,u] = pq.top(); pq.pop(); if(dist[u] < d)continue; for(auto [v,w] : a[u]){ if(dist[v] > dist[u] + w){ dist[v] = dist[u] + w; pq.push({dist[v],v}); } } } } void dfs(int u){ if(vis[u])return; vis[u] = 1; for(auto [v,w] : a[u]){ if(dist1[v] == dist1[u] + w){ dfs(v); if(dp1[v] != LINF || dp2[v] != LINF){ dp1[u] = min(dp1[u],dist2[u]); dp2[u] = min(dp2[u],dist3[u]); } dp1[u] = min(dp1[u],dp1[v]); dp2[u] = min(dp2[u],dp2[v]); } } } int main(){ cin >> n >> m; cin >> s1 >> e1; cin >> s2 >> e2; djs(s1,dist1); fr(i,0,m,1){ int u,v,w;cin >> u >> v >> w; a[u].push_back({v,w}); a[v].push_back({u,w}); } djs(s1,dist1); djs(s2,dist2); djs(e2,dist3); fill(dp1,dp1 + n + 1,LINF); fill(dp2,dp2 + n + 1,LINF); ll ans = dist2[e2]; // map<int,map<int,int>> vis; vis[e1] = 1; dp1[e1] = dist2[e1]; dp2[e1] = dist3[e1]; dfs(s1); fr(u,1,n+1,1){ ans = min({ans,dp1[u] + dist3[u],dp2[u] + dist2[u]}); } cout << ans << endl; }