#include <bits/stdc++.h> using namespace std; #define ll long long const ll INF = 1e18; // ------------------------------------------------------------ // Fast Dijkstra (min-heap, no recursion) // ------------------------------------------------------------ pair<vector<ll>, vector<vector<int>>> dijkstra_with_par(int n, const vector<vector<pair<int,ll>>> &adj, int src) { vector<ll> dist(n, INF); vector<vector<int>> par(n); dist[src] = 0; priority_queue< pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>> > pq; pq.emplace(0, src); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d != dist[u]) continue; for (auto &e : adj[u]) { int v = e.first; ll w = e.second; ll nd = d + w; if (dist[v] > nd) { dist[v] = nd; par[v].clear(); par[v].push_back(u); pq.emplace(nd, v); } else if (dist[v] == nd) { par[v].push_back(u); } } } return {dist, par}; } // ------------------------------------------------------------ // Faster Dijkstra (no parent collection) // ------------------------------------------------------------ vector<ll> dijkstra(int n, const vector<vector<pair<int,ll>>> &adj, int src) { vector<ll> dist(n, INF); dist[src] = 0; priority_queue< pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>> > pq; pq.emplace(0, src); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d != dist[u]) continue; for (auto &e : adj[u]) { int v = e.first; ll w = e.second; ll nd = d + w; if (dist[v] > nd) { dist[v] = nd; pq.emplace(nd, v); } } } return dist; } // ------------------------------------------------------------ // Main solve // ------------------------------------------------------------ void solve() { int n, m, s, t, u, v; cin >> n >> m; cin >> s >> t >> u >> v; s--, t--, u--, v--; vector<vector<pair<int,ll>>> adj(n); for (int i = 0; i < m; i++) { int a, b; ll c; cin >> a >> b >> c; a--, b--; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } // Run Dijkstra auto [dists, par] = dijkstra_with_par(n, adj, s); vector<ll> distu = dijkstra(n, adj, u); vector<ll> distv = dijkstra(n, adj, v); // Build shortest-path DAG from s to t vector<vector<int>> dag(n); // stack DFS (reverse parent edges) vector<char> used(n, 0); stack<int> st; st.push(t); used[t] = 1; while (!st.empty()) { int x = st.top(); st.pop(); for (int p : par[x]) { dag[p].push_back(x); if (!used[p]) { used[p] = 1; st.push(p); } } } // Traverse DAG from s and compute answer ll ans = INF; stack<tuple<int,ll,ll>> dfsstack; dfsstack.emplace(s, INF, INF); while (!dfsstack.empty()) { auto [x, ud, vd] = dfsstack.top(); dfsstack.pop(); ud = min(ud, distu[x]); vd = min(vd, distv[x]); ans = min(ans, ud + vd); for (int nx : dag[x]) dfsstack.emplace(nx, ud, vd); } ans = min(ans, distv[u]); cout << ans << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); }