#include <bits/stdc++.h> #include <climits> using namespace std; #define f first #define s second #define all(a) a.begin(),a.end() #define sz(a) (int)a.size() #define int long long const int N=1e5+5; const int INF=1e16; int n,m; vector<pair<int,int>>E[N]; int distx[N],disty[N]; void Dij(int s,int D[]){ priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq; for(int i=1;i<=n;++i){ D[i]=INF; } D[s]=0; pq.push({0,s}); while(!pq.empty()){ auto [d,u] =pq.top(); pq.pop(); if(D[u]!=d) continue; for(auto [v,w]:E[u]){ if(D[v]>D[u]+w){ D[v]=D[u]+w; pq.push({D[v],v}); } } } } int DP_DAG(int st,int des){ priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq; vector<int>dist(n+5,INF); dist[st]=0; pq.push({0,st}); while(!pq.empty()){ auto [d,u] =pq.top(); pq.pop(); if(dist[u]!=d) continue; for(auto [v,w]:E[u]){ if(dist[v]>dist[u]+w){ dist[v]=dist[u]+w; pq.push({dist[v],v}); } } } vector<int>can(n+1); iota(all(can),0); sort(can.begin()+1,can.begin()+n+1, [&] (int x,int y){ return dist[x]<dist[y]; }); vector<vector<int>> dp(2,vector<int>(n+5,INF)); dp[0][st] = distx[st]; dp[1][st] = distx[st] + disty[st]; for(int i=1;i<=n;++i){ int u=can[i]; for(auto [v,w]:E[u]){ if(dist[v]==dist[u]+w){ dp[0][v]=min({dp[0][v],dp[0][u],distx[v]}); dp[1][v]=min({dp[1][v],dp[1][u],dp[0][u]+disty[v]}); } } } return dp[1][des]; } void solve(){ cin>>n>>m; int s,t,x,y; cin>>s>>t; cin>>x>>y; for(int i=1;i<=m;++i) { int u,v,w;cin>>u>>v>>w; E[u].push_back({v,w}); E[v].push_back({u,w}); } Dij(x,distx); Dij(y,disty); cout<<min({DP_DAG(s,t),DP_DAG(t,s),distx[y]}); } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int T=1; while(T--) solve(); }