#include <bits/stdc++.h> #define FOR(i, a, b) for(int i = (a); i <= (b); i++) #define FOD(i, a, b) for(int i = (a); i >= (b); i--) #define file(name) if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } #define fi first #define se second #define el cout << '\n' #define maxn int(1e6 + 5) using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, int> pli; struct Edge { int u, v, w; } e[maxn]; int n, m; int A, B, C, D; ll d[5][maxn]; vector<pii> adj[maxn]; void dijkstra(int s, ll d[]) { priority_queue<pli, vector<pli>, greater<pli>> q; d[s] = 0; q.push({ 0, s }); while(!q.empty()) { int u = q.top().se; ll du = q.top().fi; q.pop(); if(du != d[u]) continue; for(pii x : adj[u]) { int v = x.fi, w = x.se; if(d[v] > d[u] + w) { d[v] = d[u] + w; q.push({ d[v], v }); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; cin >> A >> B >> C >> D; FOR(i, 1, m) { int u, v, w; cin >> u >> v >> w; e[i] = {u, v, w}; adj[u].push_back({ v, w }); adj[v].push_back({ u, w }); } memset(d, 0x3f, sizeof d); dijkstra(A, d[0]); dijkstra(B, d[1]); FOR(i, 1, n) adj[i].clear(); FOR(i, 1, m) { int u = e[i].u, v = e[i].v, w = e[i].w; if(d[0][u] + d[1][v] + w == d[0][B] || d[0][v] + d[1][u] + w == d[0][B]) { adj[u].push_back({ v, 0 }); adj[v].push_back({ u, 0 }); } else { adj[u].push_back({ v, w }); adj[v].push_back({ u, w }); } } dijkstra(C, d[2]); cout << d[2][D]; return 0; }