// #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag, tree_order_statistics_node_update>; #define ll long long #define pi pair<int,int> #define vi vector<int> #define pb push_back #define all(a) a.begin(),a.end() const ll inf = 1e18; const int mxn = 1e5+1; vector<pi> g[mxn]; vector<int> g2[mxn]; bool vis[mxn]; int n,m; void dijskitra(int s, vector<ll> &vec){ priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq; vec[s] = 0; pq.push({0,s}); while(!pq.empty()){ auto [d,u] = pq.top(); pq.pop(); if(vec[u]!=d) continue; for(auto [v,c] : g[u]) if(vec[v] > d+c) pq.push({vec[v]=d+c,v}); } } vector<int> topo; void dfs(int u){ vis[u] = 1; for(auto v : g2[u]) if(!vis[v]) dfs(v); topo.push_back(u); } void solve(){ cin >> n >> m; int s,t,s2,t2; cin >> s >> t; cin >> s2 >> t2; for(int i = 1; i <= m; i++){ int u,v,c; cin >> u >> v >> c; g[u].pb({v,c}); g[v].pb({u,c}); } vector<ll> dps(n+1,inf); dijskitra(s,dps); vector<ll> dpt(n+1,inf); dijskitra(t,dpt); vector<ll> dps2(n+1,inf); dijskitra(s2,dps2); vector<ll> dpt2(n+1,inf); dijskitra(t2,dpt2); fill(vis+1,vis+n+1,true); for(int u = 1; u <= n; u++) for(auto [v,c] : g[u]) if(dps[u] + c + dpt[v] == dps[t]){ g2[u].push_back(v); vis[u] = vis[v] = false; } for(int i = 1; i <= n; i++) if(!vis[i]) dfs(i); ll ans = dps2[t2]; for(auto u : topo){ ll dp0 = dps2[u], dp1 = dpt2[u]; for(auto v : g2[u]) dp0 = min(dp0,dps2[v]), dp1 = min(dp1,dpt2[v]); ans = min(ans,dp0 + dpt2[u]); ans = min(ans,dp1 + dps2[u]); dps2[u] = dp0; dpt2[u] = dp1; } cout << ans; } signed main(){ cin.tie(0)->sync_with_stdio(0); int t = 1; // cin >> t; while(t--){solve();} }