#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define fi first #define se second vector<vector<pair<ll, ll>>> graf; void dijkstra(int s, vector<ll>& dist) { priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; dist[s] = 0; pq.push({0, s}); while (!pq.empty()) { ll dl = pq.top().first; ll wi = pq.top().second; pq.pop(); if (dl > dist[wi]) continue; dist[wi] = dl; for (pair<ll, ll> p : graf[wi]) { ll waga = p.second; ll i = p.first; if (dl + waga < dist[i]) { dist[i] = dl + waga; pq.push({dist[i], i}); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, m, w1, w2, c, s, t, u, v; cin >> n >> m; cin >> s >> t; cin >> u >> v; graf.resize(n + 1); for (int i = 0; i < m; i++) { cin >> w1 >> w2 >> c; graf[w1].push_back({w2, c}); graf[w2].push_back({w1, c}); } priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, greater<pair<ll, pair<ll, ll>>>> pqsolve; vector<ll> dists(n + 1, 1e18); vector<ll> distt(n + 1, 1e18); vector<ll> distu(n + 1, 1e18); vector<ll> distv(n + 1, 1e18); dijkstra(s, dists); dijkstra(t, distt); dijkstra(u, distu); dijkstra(v, distv); ll odl = dists[t]; vector<vector<pair<ll, ll>>> dagst(n + 1), dagts(n + 1); vector<ll> bilansst(n + 1), bilansts(n + 1, 0), dpst(n + 1, 1e18), dpts(n + 1, 1e18), wdag(n + 1, 1e18); for (int wi = 1; wi <= n; wi++) { if (distt[wi] + dists[wi] == odl) { wdag[wi] = 1; for (pair<ll, ll> p : graf[wi]) { ll waga = p.second; ll i = p.first; if (dists[i] + distt[wi] + waga == odl) { dagst[wi].pb({i, waga}); dagts[i].pb({wi, waga}); bilansst[wi]++; bilansts[i]++; } } } } // dp z s do t queue<int> q; dpst[s] = distu[s]; q.push(s); while (!q.empty()) { int wi = q.front(); q.pop(); dpst[wi] = distu[wi]; for (pair<ll, ll> p : dagst[wi]) { ll waga = p.second; ll i = p.first; dpst[wi] = min(dpst[i], dpst[wi]); } for (pair<ll, ll> p : dagts[wi]) { ll waga = p.second; ll i = p.first; bilansst[i]--; if (bilansst[i] == 0) q.push(i); } } // dp z t do s dpts[t] = distu[t]; q.push(t); while (!q.empty()) { int wi = q.front(); q.pop(); dpts[wi] = distu[wi]; for (pair<ll, ll> p : dagts[wi]) { ll waga = p.second; ll i = p.first; dpts[wi] = min(dpts[i], dpts[wi]); } for (pair<ll, ll> p : dagst[wi]) { ll waga = p.second; ll i = p.first; bilansts[i]--; if (bilansts[i] == 0) q.push(i); } } // wyniki ll wynik = distu[v]; for (int i = 1; i <= n; i++) { if (wdag[i] == 1) { wynik = min(wynik, min(dpst[i], dpts[i]) + distv[i]); } } cout << wynik << endl; }