#include <bits/stdc++.h> using namespace std; #define ll long long int N, M, S, T, U, V; ll distS[100005], distT[100005], distU[100005], distV[100005]; vector<pair<int,ll>> path[100005]; vector<int> adj1[100005], adj2[100005]; ll dp1[100005], dp2[100005]; vector<tuple<int,int,ll>> Edge; priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq; void dfs1(int u, int pa) { dp1[u] = min({dp1[u], distU[u], dp1[pa]}); dp2[u] = min({dp2[u], dp1[u] + distV[u], dp2[pa]}); for (auto v : adj1[u]) { dfs1(v, u); } } void dfs2(int u, int pa) { dp1[u] = min({dp1[u], distU[u], dp1[pa]}); dp2[u] = min({dp2[u], dp1[u] + distV[u], dp2[pa]}); for (auto v : adj2[u]) { dfs2(v, u); } } int main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> N >> M >> S >> T >> U >> V; for (int i = 0; i < 100005; i++) { distS[i] = 1e18; distT[i] = 1e18; distU[i] = 1e18; distV[i] = 1e18; } for (int i = 0; i < M; i++) { int u, v, w; cin >> u >> v >> w; path[u].emplace_back(v, w); path[v].emplace_back(u, w); Edge.emplace_back(u, v, w); } // calc distS distS[S] = 0; pq.emplace(0, S); while (!pq.empty()) { auto [w, u] = pq.top(); pq.pop(); if (distS[u] < w) continue; distS[u] = w; for (auto [v, ww] : path[u]) { if (distS[v] <= w + ww) continue; distS[v] = w + ww; pq.emplace(w + ww, v); } } // calc distT distT[T] = 0; pq.emplace(0, T); while (!pq.empty()) { auto [w, u] = pq.top(); pq.pop(); if (distT[u] < w) continue; distT[u] = w; for (auto [v, ww] : path[u]) { if (distT[v] <= w + ww) continue; distT[v] = w + ww; pq.emplace(w + ww, v); } } // calc distU distU[U] = 0; pq.emplace(0, U); while (!pq.empty()) { auto [w, u] = pq.top(); pq.pop(); if (distU[u] < w) continue; distU[u] = w; for (auto [v, ww] : path[u]) { if (distU[v] <= w + ww) continue; distU[v] = w + ww; pq.emplace(w + ww, v); } } // calc distV distV[V] = 0; pq.emplace(0, V); while (!pq.empty()) { auto [w, u] = pq.top(); pq.pop(); if (distV[u] < w) continue; distV[u] = w; for (auto [v, ww] : path[u]) { if (distV[v] <= w + ww) continue; distV[v] = w + ww; pq.emplace(w + ww, v); } } ll min_dist = distS[T]; for (auto [u, v, w] : Edge) { if (distS[v] + w + distT[u] == min_dist) { adj1[v].emplace_back(u); adj2[u].emplace_back(v); } if (distS[u] + w + distT[v] == min_dist) { adj2[v].emplace_back(u); adj1[u].emplace_back(v); } } ll ans = distU[V]; // process adj1 fill(dp1, dp1 + 100005, 1e18); fill(dp2, dp2 + 100005, 1e18); dfs1(S, 0); ans = min(dp2[T], ans); // process adj2 fill(dp1, dp1 + 100005, 1e18); fill(dp2, dp2 + 100005, 1e18); dfs2(T, 0); ans = min(dp2[S], ans); cout << ans; }