#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
typedef pair<int, pii> pip;
typedef pair<pii, int> ppi;
typedef pair<pii, pii> ppp;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 10;
const int LLINF = 2e18 + 10;
const int MAXN = 2e5 + 10;
int n;
vector<pii> adj[MAXN];
vector<int> dijkstra(vector<int> &start_distances) {
vector<int> dist(n + 1);
vector<int> mrk(n + 1, false);
priority_queue<pii> pq;
for (int i = 1; i <= n; i++) {
dist[i] = start_distances[i];
pq.push({-dist[i], i});
}
while (!pq.empty()) {
int v = pq.top().second;
pq.pop();
if (mrk[v]) continue;
mrk[v] = true;
for (auto [w, c]: adj[v]) {
if (!mrk[w] && dist[w] > dist[v] + c) {
dist[w] = dist[v] + c;
pq.push({-dist[w], w});
}
}
}
return dist;
}
vector<int> commuter_pass(
vector<int> &start_distances,
vector<int> &dh,
vector<int> &ds,
int school) {
map<pii, int> dist;
set<pii> mrk;
priority_queue<ppp> pq;
vector<bool> in_path(n + 1, false);
for (int i = 1; i <= n; i++) {
int start_dist;
if (dh[i] + ds[i] == dh[school]) {
start_dist = start_distances[i];
in_path[i] = true;
} else {
start_dist = LLINF;
}
dist[{i, 0}] = start_dist;
pq.push({{-start_dist, -start_dist}, {i, 0}});
}
for (int v = 1; v <= n; v++) {
for (auto [w, c]: adj[v]) {
dist[{w, v}] = LLINF;
pq.push({{-LLINF, -LLINF}, {v, w}});
}
}
while (!pq.empty()) {
ppp x = pq.top();
int d = -x.first.first;
int cp = -x.first.second;
int v = x.second.first;
int p = x.second.second;
pq.pop();
if (d == LLINF || mrk.count({v, p})) continue;
mrk.insert({v, p});
for (auto [w, c]: adj[v]) {
if ((p == 0 && in_path[w]) || dh[p] + cp + c + ds[w] == dh[school] || ds[p] + cp + c + dh[w] == dh[school]) {
int dold = dist[{w, v}];
int dnew = dist[{v, p}];
if (!mrk.count({w, v}) && dold > dnew) {
dist[{w, v}] = dnew;
pq.push({{-dnew, -c}, {w, v}});
}
}
}
}
vector<int> ret(n + 1, LLINF);
for (auto [k, val]: dist) {
ret[k.first] = min(ret[k.first], val);
}
return ret;
}
void solve() {
int m, house, school, book_u, book_v;
cin >> n >> m >> house >> school >> book_u >> book_v;
while (m--) {
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
vector<int> dists(n + 1, LLINF);
dists[house] = 0;
vector<int> d_house = dijkstra(dists);
dists[house] = LLINF;
dists[school] = 0;
vector<int> d_school = dijkstra(dists);
dists[school] = LLINF;
dists[book_u] = 0;
vector<int> step_0 = dijkstra(dists);
// inside commuter pass
vector<int> step_1 = commuter_pass(step_0, d_house, d_school, school);
// after leaving commuter pass
vector<int> step_2 = dijkstra(step_1);
cout << min({ step_0[book_v], step_1[book_v], step_2[book_v] }) << endl;
}
int32_t main() {
solve();
return 0;
}
