#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) -> vl { vl dis(n, inf); 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; pq.push({dis[v], v}); } } } return dis; }; vl dis_u = dijkstra(U); vl dis_v = dijkstra(V); vl dis(n, inf), mn_u(n, inf), mn_v(n, inf); using T = pair<ll, int>; priority_queue<T, vector<T>, greater<>> pq; pq.push({0, src}); mn_u[src] = dis_u[src]; mn_v[src] = dis_v[src]; while (SZ(pq)) { auto [w, u] = pq.top(); pq.pop(); if (u == dest) break; if (w > dis[u]) continue; for (auto [v, w2]: adj[u]) { if (dis[v] > w + w2) { dis[v] = w + w2; mn_u[v] = min(mn_u[u], dis_u[v]); mn_v[v] = min(mn_v[u], dis_v[v]); pq.push({dis[v], v}); } else if (dis[v] == w + w2) { mn_u[v] = min({mn_u[v], mn_u[u], dis_u[v]}); mn_v[v] = min({mn_v[v], mn_v[u], dis_v[v]}); } } } // cerr << dis[dest] << '\n'; cout << min(mn_u[dest] + mn_v[dest], dis_u[V]) << '\n'; } signed main() { cin.tie(nullptr)->sync_with_stdio(false); sol(); }