/* OJUZ commuter pass if sps[i] + spt[i] == sps[t]: can be in sp convert this to DAG dp on DAG dp[i][0] -> minimize x dp[i][1] -> minimize y */ #include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll BIG = 1e18; vector<ll> shortest_paths(ll n, vector<vector<pair<ll, ll>>> &adj){ vector<ll> res(adj.size(), LLONG_MAX); res[n] = 0; priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; pq.push({0, n}); while(!pq.empty()){ auto [dist, c] = pq.top(); pq.pop(); if(res[c] != dist) continue; for(pair<ll, ll> e:adj[c]){ if(res[e.first] > dist + e.second){ res[e.first] = dist + e.second; pq.push({res[e.first], e.first}); } } } return res; } int main(){ ll n,m;cin>>n>>m; ll s,t;cin>>s>>t; ll u,v;cin>>u>>v; s--,t--,u--,v--; vector<vector<pair<ll, ll>>> adj(n); for(int i=0;i<m;i++){ int a,b,c;cin>>a>>b>>c;a--,b--; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } vector<ll> sps(n),spt(n),spu(n),spv(n); sps = shortest_paths(s, adj); spt = shortest_paths(t, adj); spu = shortest_paths(u, adj); spv = shortest_paths(v, adj); vector<vector<ll>> DAGadj(n); vector<ll> back(n); for(ll i=0;i<n;i++){ if(sps[i] + spt[i] != sps[t]) continue; for(pair<ll, ll> e:adj[i]){ if(sps[e.first] + spt[e.first] != sps[t]) continue; if(sps[i] + e.second == sps[e.first]){ DAGadj[i].push_back(e.first); back[e.first]++; } } } vector<array<ll, 4>> dp(n, {BIG, BIG, BIG, BIG}); vector<ll> topo; stack<ll> q; for(ll i=0;i<n;i++){ if(back[i] == 0) q.push(i); } while(!q.empty()){ ll c = q.top(); q.pop(); topo.push_back(c); for(ll e:DAGadj[c]){ back[e]--; if(back[e] == 0) q.push(e); } } for(ll i:topo){ if(spu[i] <= dp[i][0]){ dp[i][0] = spu[i]; dp[i][1] = min(dp[i][1], spv[i]); } if(spv[i] <= dp[i][3]){ dp[i][2] = min(dp[i][2], spu[i]); dp[i][3] = spv[i]; } for(ll e:DAGadj[i]){ if(dp[i][0] <= dp[e][0]){ dp[e][0] = dp[i][0]; dp[e][1] = min(dp[i][1], spv[i]); } if(dp[i][3] <= dp[e][3]){ dp[e][2] = min(dp[i][2], spu[i]); dp[e][3] = dp[i][3]; } } } // for(auto i:dp){ // for(auto j:i) // cout << j << ' '; // cout << '\n'; // } ll absmn = BIG; for(ll i=0;i<n;i++){ absmn = min(absmn, min(dp[i][0] + dp[i][1], dp[i][2] + dp[i][3])); } cout << absmn << '\n'; }