#include <bits/stdc++.h> #include <queue> #include <vector> using namespace std; #define ll long long #define pb push_back #define F first #define S second #define pii pair<int,int> #define vi vector<int> #define vpii vector<pii> #define loop(i,n) sloop(0,i,n) #define sloop(s, i, n) for(int i=(s);i<(n);i++) #define rloop(i,n) rsloop(0,i,n) #define rsloop(s,i,n) for(int i=(n);i-->(s);) #define all(v) (v).begin(),(v).end() #define nie {cout<<"No\n";return;} #define tak {cout<<"Yes\n";return;} #ifdef DEBUG #define DBG cout << __LINE__ << endl; #else #define DBG #endif //int xses[8] = {-1,1,0,0,-1,1,1,-1}; //int yses[8] = {0,0,-1,1,-1,1,-1,1}; #define int ll vector<vpii>g; void dij(vi&odl,int start){ priority_queue<pii,vpii,greater<pii>>pq; pq.push({0,start}); while(pq.size()){ auto [w,cur] = pq.top(); pq.pop(); if(odl[cur]!=INT_MAX)continue; odl[cur]=w; for(pii i:g[cur]){ if(odl[i.F]==INT_MAX) pq.push({i.S+w,i.F}); } } } void solve() { int n,m; cin>>n>>m; g.assign(n,vpii()); int s,t,u,v; cin>>s>>t>>u>>v; --s;--t;--u;--v; loop(i,m){ int a,b,c; cin>>a>>b>>c; --a;--b; g[a].pb({b,c}); g[b].pb({a,c}); } vector<vi> odl(4,vi(n,INT_MAX)); //s, t, u, v dij(odl[0],s); dij(odl[1],t); dij(odl[2],u); dij(odl[3],v); // 1. robie daga // 2. dp na dagu dp[i] ile odległości potrzebuje żeby dotrzeć z i do v // 3. odpowiedź to min z odl(u,i) dp[i] vector<vi> dag(n); loop(i,n){ for(pii j:g[i]){ if(odl[0][i]+odl[1][j.F]+j.S==odl[0][t]){ dag[i].pb(j.F); } } } vi dp1(n,INT_MAX); vi dp2(n,INT_MAX); auto liczDP1 = [&](auto &Sf,int node) -> void{ if(dp1[node]!=INT_MAX)return; dp1[node] = odl[3][node]; for(int i:dag[node]){ if(dp1[i]==INT_MAX)Sf(Sf,i); dp1[node]=min(dp1[node],dp1[i]); } }; auto liczDP2 = [&](auto &Sf,int node) -> void{ if(dp2[node]!=INT_MAX)return; dp2[node] = odl[2][node]; for(int i:dag[node]){ if(dp2[i]==INT_MAX)Sf(Sf,i); dp2[node]=min(dp2[node],dp2[i]); } }; loop(i,n)liczDP1(liczDP1,i); loop(i,n)liczDP2(liczDP2,i); int res=odl[2][v]; loop(i,n){ res=min(res,odl[2][i]+dp1[i]); res=min(res,odl[3][i]+dp2[i]); } /* loop(i,n){ cout<<i<<": "; for(int j:dag[i]){ cout<<j<<' '; } cout<<'\n'; } */ /* loop(i,n)cout<<dp[i]<<' '; cout<<'\n'; */ cout<<res<<'\n'; } signed main() { cin.tie(0); ios_base::sync_with_stdio(0); int t=1; //cin>>t; loop(i,t) { #ifdef DEBUG if(t!=1) { cout<<"Test no. "<<i+1<<endl; } #endif solve(); } #ifdef DEBUG cout << '\n'; #endif return 0; }