#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 7; int N, M, A, B, C, D; bool vis[maxn]; vector<pair<int, int>> ed, adj[maxn]; vector<int> dag[maxn]; struct vertex{ long long dis; int state, ver; bool operator > (const vertex &other) const {return dis > other.dis;} }; void dijkstra1(int s, vector<long long> &dis) { priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q; q.push({dis[s] = 0, s}); while(!q.empty()){ auto [d, v] = q.top(); q.pop(); if(d > dis[v]) continue; for(auto &[x, w]: adj[v]){ if(d + w >= dis[x]) continue; q.push({dis[x] = d + w, x}); } } } long long dijkstra2(){ std::array<std::vector<long long>, 3> dis; for(int i = 0; i < 3; ++i) dis[i].assign(N + 1, (long long)1e18); std::priority_queue<vertex, std::vector<vertex>, std::greater<vertex>> pq; pq.push({dis[0][C] = 0, 0, C}); while(!pq.empty()){ auto [d, s, v] = pq.top(); pq.pop(); if(d > dis[s][v]) continue; if(s == 1){ for(int &x: dag[v]){ if(d >= dis[1][x]) continue; pq.push({dis[1][x] = d, 1, x}); } } else{ for(auto &[x, w]: adj[v]){ if(d + w >= dis[s][x]) continue; pq.push({dis[s][x] = d + w, s, x}); } } if(s < 2 && dis[s + 1][v] > d){ pq.push({dis[s + 1][v] = d, s + 1, v}); } } return dis[2][D]; } int main() { // freopen("data.txt", "r", stdin); // freopen("path.inp", "r", stdin); // freopen("path.out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> M >> A >> B >> C >> D; for(int u, v, w; M--;){ cin >> u >> v >> w; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } vector <long long> fromA(N + 1, (long long)1e18); dijkstra1(A, fromA); { queue<int> q; q.push(B); vis[B] = true; while(!q.empty()) { int v = q.front(); q.pop(); for(auto &[x, w]: adj[v]){ if(fromA[v] - w != fromA[x]) continue; ed.emplace_back(x, v); if(!vis[x]) vis[x] = true, q.push(x); } } } for(auto &[u, v]: ed) dag[u].push_back(v); long long ans = dijkstra2(); for(int i = 1; i <= N; ++i) dag[i].clear(); for(auto &[u, v]: ed) dag[v].push_back(u); ans = min(ans, dijkstra2()); cout << ans; return 0; }