#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 D[N]; int par[N]; void Dij(int s){ priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq; for(int i=1;i<=n;++i){ D[i]=INF; par[i]=i; } 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}); par[v]=u; } } } } vector<pair<int,int>>can; void Dij2(int s){ priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq; for(int i=1;i<=n;++i){ D[i]=INF; par[i]=i; } 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]){ int temp=D[u]+w; int u1=min(u,v); int v1=max(u,v); int p=lower_bound(all(can),make_pair(u1,v1))-can.begin(); if(can[p]==make_pair(u1,v1)) temp=0; if(D[v]>temp){ D[v]=temp; pq.push({D[v],v}); par[v]=u; } } } } void solve(){ cin>>n>>m; int s,t; cin>>s>>t; int U,V;cin>>U>>V; 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(s); while(par[t]!=t){ can.push_back({min(t,par[t]),max(t,par[t])}); t=par[t]; } sort(all(can)); Dij2(U); cout<<D[V]; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int T=1; while(T--) solve(); }