#include <bits/stdc++.h> // solved by bekagg #define int long long #define ent '\n' #define pb push_back #define all(x) x.begin(),x.end() #define PRaim_bek_abi ios_base::sync_with_stdio(0);cin.tie(0); using namespace std; const int N = 2e5+5; const int MOD = 1e9+7; int n , m , ds[N] , dt[N] , du[N] , dv[N] , x[N] , y[N] , w[N] , cnt[N] , ans = 10000000000000000 , dp[N][2]; bool us[N]; vector<pair<int , int>> g[N]; vector<int> d[N] , o[N]; void create_ds(int start){ for (int i = 1; i <= n; i++) ds[i] = dt[i] = du[i] = dv[i] = dp[i][0] = dp[i][1] = 10000000000000000; set< pair<int , int> > st; ds[start] = 0; st.insert({0 , start}); while(!st.empty()){ int v = (*st.begin()).second; st.erase(st.begin()); for (auto [to , c] : g[v]){ if (ds[to] > ds[v] + c){ if (st.find({ds[to] , to}) != st.end()) st.erase(st.find({ds[to] , to})); ds[to] = ds[v] + c; st.insert({ds[to] , to}); } } } } void create_dt(int start){ dt[start] = 0; set< pair<int , int> > st; st.insert({0 , start}); while(!st.empty()){ int v = (*st.begin()).second; st.erase(st.begin()); for (auto [to , c] : g[v]){ if (dt[to] > dt[v] + c){ if (st.find({dt[to] , to}) != st.end()) st.erase(st.find({dt[to] , to})); dt[to] = dt[v] + c; st.insert({dt[to] , to}); } } } } void create_du(int start){ du[start] = 0; set< pair<int , int> > st; st.insert({0 , start}); while(!st.empty()){ int v = (*st.begin()).second; st.erase(st.begin()); for (auto [to , c] : g[v]){ if (du[to] > du[v] + c){ if (st.find({du[to] , to}) != st.end()) st.erase(st.find({du[to] , to})); du[to] = du[v] + c; st.insert({du[to] , to}); } } } } void create_dv(int start){ dv[start] = 0; set< pair<int , int> > st; st.insert({0 , start}); while(!st.empty()){ int v = (*st.begin()).second; st.erase(st.begin()); for (auto [to , c] : g[v]){ if (dv[to] > dv[v] + c){ if (st.find({dv[to] , to}) != st.end()) st.erase(st.find({dv[to] , to})); dv[to] = dv[v] + c; st.insert({dv[to] , to}); } } } } void dfs(int v){ dp[v][0] = min(dp[v][0] , du[v]); dp[v][1] = min(dp[v][1] , dv[v]); ans = min({ans , dp[v][0] + dv[v] , dp[v][1] + du[v]}); for (auto to : d[v]){ dp[to][0] = min(dp[to][0] , dp[v][0]); dp[to][1] = min(dp[to][1] , dp[v][1]); ++cnt[to]; if (cnt[to] == o[to].size()) dfs(to); } } void arkanefury228(){ int s , t , u , v; cin >> n >> m >> s >> t >> u >> v; for (int i = 1; i <= m; i++){ cin >> x[i] >> y[i] >> w[i]; g[x[i]].pb({y[i] , w[i]}); g[y[i]].pb({x[i] , w[i]}); } create_ds(s); create_dt(t); create_du(u); create_dv(v); for (int i = 1; i <= m; i++){ if (ds[x[i]] > ds[y[i]]) swap(x[i] , y[i]); if (ds[t] == ds[x[i]] + dt[y[i]] + w[i]){ d[x[i]].pb(y[i]); o[y[i]].pb(x[i]); } } dfs(s); cout << ans; } signed main(){ PRaim_bek_abi int t=1; //cin>>t; for (int respagold = 1; respagold <= t; respagold++) arkanefury228(); }