/** * Author: trviet * Studies at: Le Hong Phong High School for the Gifted **/ #include <bits/stdc++.h> using namespace std; using lli = long long; constexpr int maxn = 2e5 + 5; constexpr long long inf = 1e18; int n, m, src[4], mark[maxn]; lli d[4][maxn], ans = inf, dp[maxn][2]; vector<pair<int, int>> g[maxn]; vector<int> dag[maxn]; void Dijkstra(int k) { fill(d[k], d[k] + 1 + n, inf); priority_queue<pair<lli, int>> pq; pq.push({0, src[k]}); d[k][src[k]] = 0; while (!pq.empty()) { int x = pq.top().second; pq.pop(); for (int i = 0; i < g[x].size(); ++i) { int y = g[x][i].first, w = g[x][i].second; if (d[k][y] > d[k][x] + w) { d[k][y] = d[k][x] + w; pq.push({-d[k][y], y}); } } } } void depth_search(int u) { if (mark[u]) return; mark[u] = 1, dp[u][0] = dp[u][1] = inf; for (int v : dag[u]) { depth_search(v); dp[u][0] = min(dp[u][0], min(dp[v][0], d[2][v])); dp[u][1] = min(dp[u][1], min(dp[v][1], d[3][v])); } ans = min(ans, dp[u][0] + d[3][u]); ans = min(ans, dp[u][1] + d[2][u]); } void ReadData() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 0; i < 4; ++i) cin >> src[i]; for (int i = 0; i < m; ++i) { int x, y, w; cin >> x >> y >> w; g[x].push_back({y, w}); g[y].push_back({x, w}); } } void Solve() { for (int i = 0; i < 4; ++i) Dijkstra(i); for (int i = 1; i <= n; ++i) for (int t = 0; t < g[i].size(); ++t) { int j = g[i][t].first, w = g[i][t].second; if (d[0][i] + w + d[1][j] == d[0][src[1]]) dag[i].push_back(j); } depth_search(src[0]); cout << min(d[2][src[3]], ans); } int main() { ReadData(); Solve(); return 0; }