/** * Author: wannaStayWithU * Date: 2/2/2569 */ #include <bits/stdc++.h> using namespace std; #define int long long vector<int> dij(vector<pair<int, int>> ap[], int n, int s) { vector<int> mn(n + 1, 1e18); mn[s] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, s}); while (pq.size()) { auto [d, u] = pq.top(); pq.pop(); if (mn[u] < d) continue; for (auto& [v, w] : ap[u]) { if (mn[v] > d + w) { mn[v] = d + w; pq.push({mn[v], v}); } } } return mn; } vector<array<int, 3>> dij2(vector<pair<int, int>> ap[], vector<int> &ds, vector<int> &dt, int n, int s) { vector<array<int, 3>> mn(n + 1); for (int i = 1; i <= n; i++) mn[i] = {(int)1e18, ds[i], dt[i]}; mn[s] = {0, ds[s], dt[s]}; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, s}); while (pq.size()) { auto [d, u] = pq.top(); pq.pop(); if (mn[u][0] < d) continue; for (auto& [v, w] : ap[u]) { if (mn[v][0] >= d + w) { mn[v][1] = min(mn[u][1], ds[v]); mn[v][2] = min(mn[u][2], dt[v]); if (mn[v][0] > d + w) pq.push({d + w, v}); mn[v][0] = d + w; } } } return mn; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; int s, t, a, b; cin >> s >> t >> a >> b; vector<pair<int, int>> ap[n + 1]; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; ap[u].push_back({v, w}); ap[v].push_back({u, w}); } vector<int> ds = dij(ap, n, a); vector<int> dt = dij(ap, n, b); vector<array<int, 3>> ans1 = dij2(ap, ds, dt, n, s); vector<array<int, 3>> ans2 = dij2(ap, ds, dt, n, t); int ans = 1e18; for (int i = 1; i <= n; i++) { if (ans1[t][0] == ans1[i][0] + ans2[i][0]) { //cout << i << '\n'; //cout << ans1[i][1] << ' ' << ans1[i][2] << ' ' << ans2[i][1] << ' ' << ans2[i][2] << '\n'; ans = min({ans, ans1[i][1] + ans2[i][2], ans1[i][2] + ans2[i][1]}); } } cout << min(ds[b], ans); return 0; } /* */