#include <bits/stdc++.h> using namespace std; #define ll long long const ll nx=2e5+5, inf=1e18; ll n, m, s, t, x, y, u, v, w, dp[nx][2], res=inf; vector<ll> mns(nx, inf), mnt(nx, inf), mnx(nx, inf), mny(nx, inf); vector<pair<ll, ll>> adj[nx]; void dijkstra(ll st, vector<ll> &mn) { mn[st]=0; priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; pq.push({0, st}); while (!pq.empty()) { auto [cw, u]=pq.top(); pq.pop(); if (cw>mn[u]) pq.pop(); for (auto [v, w]:adj[u]) if (mn[v]>mn[u]+cw) mn[v]=mn[u]+w, pq.push({mn[v], v}); } } void dfs(int u) { dp[u][0]=mnx[u]; dp[u][1]=mny[u]; for (auto [v, w]:adj[u]) { if (mns[v]+mnt[v]!=mns[t]||mns[v]<mns[u]) continue; dfs(v); dp[u][0]=min(dp[u][0], dp[v][0]); dp[u][1]=min(dp[u][1], dp[v][1]); } // cout<<"debug "<<u<<' '<<dp[u][0]<<' '<<dp[u][1]<<'\n'; res=min(res, dp[u][0]+dp[u][1]); } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>m>>s>>t>>x>>y; for (int i=1; i<=m; i++) cin>>u>>v>>w, adj[u].push_back({v, w}), adj[v].push_back({u, w}); dijkstra(s, mns); dijkstra(t, mnt); dijkstra(x, mnx); dijkstra(y, mny); dfs(s); cout<<min(res, mnx[y]); }