#include <bits/stdc++.h> #define F first #define S second #define SZ(x) ((int)(x).size()) #define ALL(x) x.begin(), x.end() using namespace std; using ll = long long; using vi = vector<int>; using vl = vector<ll>; using vvi = vector<vi>; using vvl = vector<vl>; using pii = pair<int, int>; using pll = pair<ll, ll>; using vii = vector<pii>; using vll = vector<pll>; const ll inf = 0x3f3f3f3f3f3f3f3f; void sol() { int n, m, src, dest, U, V; cin >> n >> m >> src >> dest >> U >> V; --src, --dest, --U, --V; vector<vii> adj(n); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; adj[--u].push_back({--v, w}); adj[v].push_back({u, w}); } auto dijkstra = [n, m, &adj](int src) -> pair<vl, vvi> { vl dis(n, inf); vvi from(n); dis[src] = 0; using T = pair<ll, int>; priority_queue<T, vector<T>, greater<>> pq; pq.push({0, src}); while (SZ(pq)) { auto [w, u] = pq.top(); pq.pop(); if (w > dis[u]) continue; for (auto [v, w2]: adj[u]) { if (dis[v] > w + w2) { dis[v] = w + w2; from[v] = {u}; pq.push({dis[v], v}); } else if (dis[v] == w + w2) { from[v].push_back(u); } } } return {dis, from}; }; auto [dis_src, from] = dijkstra(src); vl dis_u = dijkstra(U).F; vl dis_v = dijkstra(V).F; vi deg(n, 0); vi vec; vector<bool>vis(n); function<void(int)> dfs = [&](int u) -> void { vis[u] = 1; vec.push_back(u); for (int v: from[u]) if (!vis[v]) dfs(v); }; dfs(dest); for (int u: vec) for (int v: from[u]) deg[v]++; vl mn_u(n, inf), mn_v(n, inf); queue<int> qq({dest}); ll ans = dis_u[V]; while (SZ(qq)) { int u = qq.front(); qq.pop(); mn_u[u] = min(mn_u[u], dis_u[u]); mn_v[u] = min(mn_v[u], dis_v[u]); ans = min(ans, mn_u[u] + dis_v[u]); ans = min(ans, mn_v[u] + dis_u[u]); // cerr << u << '\n'; // cerr << mn_u[u] << ' ' << dis_v[u] << '\n'; // cerr << mn_v[u] << ' ' << dis_u[u] << '\n'; for (int v: from[u]) { mn_u[v] = min(mn_u[v], mn_u[u]); mn_v[v] = min(mn_v[v], mn_v[u]); if (--deg[v] == 0) { qq.push(v); } } } cout << ans << '\n'; } signed main() { cin.tie(nullptr)->sync_with_stdio(false); sol(); }