#include <bits/stdc++.h> using namespace std; int numNode, numEdge, S, T, U, V; struct Edge { int u, v, w; int other(int x) { return (u ^ v ^ x); } }; #define MAX_NODE 100100 #define MAX_EDGE 200200 vector<int> topo; vector<int> adj[MAX_NODE], dad[MAX_NODE]; long long distS[MAX_NODE], distT[MAX_NODE], distU[MAX_NODE], distV[MAX_NODE], res[MAX_NODE]; bool vis[MAX_NODE]; Edge edges[MAX_EDGE]; void Dijkstra(int s, long long *dist) { memset(dist, 0x3f, (numNode + 1) * sizeof(long long)); priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q; dist[s] = 0; q.push(make_pair(dist[s], s)); while (!q.empty()) { int u = q.top().second; long long du = q.top().first; q.pop(); if (du != dist[u]) continue; for (int id : adj[u]) { int v = edges[id].other(u); int w = edges[id].w; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; q.push(make_pair(dist[v], v)); } } } } void buildTopo(int u) { vis[u] = true; for (int v : dad[u]) { if (!vis[v]) buildTopo(v); } topo.push_back(u); } long long getAns(int en, long long *distFrom, long long *distTo) { memset(res, 0x3f, sizeof(res)); long long ans = distFrom[en]; for (int u : topo) { res[u] = min(res[u], distFrom[u]); for (int v : dad[u]) res[v] = min(res[v], res[u]); ans = min(ans, res[u] + distTo[u]); } return ans; } int main() { ios_base::sync_with_stdio(false);cin.tie(nullptr); cin >> numNode >> numEdge; cin >> S >> T; cin >> U >> V; for (int i = 1; i <= numEdge; ++i) { int u, v, w; cin >> u >> v >> w; edges[i] = {u, v, w}; adj[u].push_back(i); adj[v].push_back(i); } Dijkstra(S, distS); Dijkstra(T, distT); Dijkstra(U, distU); Dijkstra(V, distV); for (int i = 1; i <= numEdge; ++i) { int u = edges[i].u, v = edges[i].v, w = edges[i].w; if (distS[u] + w == distS[v] && distS[T] == distS[v] + distT[v]) { dad[u].push_back(v); } if (distS[v] + w == distS[u] && distS[T] == distS[u] + distT[u]) { dad[v].push_back(u); } } buildTopo(S); reverse(topo.begin(), topo.end()); cout << min(getAns(V, distU, distV), getAns(U, distV, distU)); return 0; }