#include <bits/stdc++.h> using namespace std; #define ll long long const ll INF = (ll)4e18; struct Edge{ int to; ll w; }; int n,m; vector<vector<Edge>> adj; vector<ll> dijkstra(int src){ vector<ll> dist(n,INF); priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<>> pq; dist[src]=0; pq.push({0,src}); while(!pq.empty()){ auto [d,u]=pq.top(); pq.pop(); if(d!=dist[u]) continue; for(auto &e:adj[u]){ ll nd= d + e.w; if(nd<dist[e.to]){ dist[e.to]=nd; pq.push({nd, e.to}); } } } return dist; } ll solve(int root, int target, const vector<ll> &dx, const vector<ll> &dy){ vector<ll> dist = dijkstra(root); vector<vector<int>> dag(n); for(int u=0;u<n;u++){ if(dist[u]==INF) continue; for(auto &e:adj[u]){ if(dist[e.to]==dist[u]+e.w){ dag[u].push_back(e.to); } } } vector<int> order(n); iota(order.begin(),order.end(),0); sort(order.begin(),order.end(),[&](int a,int b){ return dist[a]<dist[b]; }); vector<ll> dp0(n,INF),dp1(n,INF); dp0[root]=dx[root]; dp1[root]=dx[root]+dy[root]; for(int u:order){ if(dist[u]==INF) continue; for(int v:dag[u]){ dp0[v]=min(dp0[v],dp0[u]); dp0[v]=min(dp0[v],dx[v]); dp1[v]=min(dp1[v],dp1[u]); dp1[v]=min(dp1[v],dp0[u]+dy[v]); } } return dp1[target]; } int main(){ cin.tie(NULL)->ios_base::sync_with_stdio(false); int s,t,u,v; cin >> n >> m >> s >> t >> u >> v; s--, t--, u--, v--; adj.assign(n,{}); for(int i=0;i<m;i++){ int a,b; ll c; cin >> a >> b >> c; a--, b--; adj[a].push_back({b,c}); adj[b].push_back({a,c}); } vector<ll> dx=dijkstra(u); vector<ll> dy=dijkstra(v); ll ans=dx[v]; ans=min(ans,solve(s,t,dx,dy)); ans=min(ans,solve(t,s,dx,dy)); cout << ans; return 0; }