#include <bits/stdc++.h> using namespace std; #define ll long long const ll INF = 1e18; struct Edge { int v; ll w; }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; int s, t, u, v; cin >> s >> t >> u >> v; s--, t--, u--, v--; vector<vector<Edge>> 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}); } auto dijkstra = [&](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.v; ll w = e.w; if(dist[v] > d + w){ dist[v] = d + w; par[v].clear(); par[v].push_back(u); pq.emplace(dist[v], v); } else if(dist[v] == d + w){ par[v].push_back(u); } } } return make_pair(dist, par); }; auto [dists, par] = dijkstra(s); auto [distu, _1] = dijkstra(u); auto [distv, _2] = dijkstra(v); // Build shortest-path DAG from s to t vector<vector<int>> new_edges(n); stack<int> st2; vector<char> vis(n, 0); st2.push(t); vis[t] = 1; while(!st2.empty()){ int x = st2.top(); st2.pop(); for(int p : par[x]){ new_edges[p].push_back(x); // O(1) if(!vis[p]){ vis[p] = 1; st2.push(p); } } } ll ans = INF; // DFS without recursion stack<tuple<int,ll,ll>> st; st.emplace(s, INF, INF); while(!st.empty()){ auto [x, ud, vd] = st.top(); st.pop(); ud = min(ud, distu[x]); vd = min(vd, distv[x]); ans = min(ans, ud + vd); for(int nx : new_edges[x]) st.emplace(nx, ud, vd); } ans = min(ans, distv[u]); cout << ans << "\n"; }