#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;
}
void print_map(map<pii, int> &mp) {
for (auto [k, val]: mp) {
cout << k.first << " " << k.second << " -> " << val << endl;
}
}
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++) {
if (dh[i] + ds[i] == dh[school]) {
dist[{i, 0}] = start_distances[i];
in_path[i] = true;
} else {
dist[{i, 0}] = LLINF;
}
pq.push({{-dist[{i, 0}], -dist[{i, 0}]}, {i, 0}});
}
for (int v = 1; v <= n; v++) {
for (auto [w, c]: adj[v]) {
dist[{w, v}] = LLINF;
pq.push({{-dist[{w, v}], -dist[{w, v}]}, {v, w}});
}
}
// print_map(dist);
while (!pq.empty()) {
int d = -pq.top().first.first;
int cp = -pq.top().first.second;
int v = pq.top().second.first;
int p = pq.top().second.second;
pq.pop();
if (d == LLINF || mrk.count({v, p})) continue;
mrk.insert({v, p});
// cout << "processing " << v << " " << p << endl;
for (auto [w, c]: adj[v]) {
// printf("looking at %lld -> %lld -> %lld\n", p, v, w);
if ((p == 0 && in_path[w]) || dh[p] + cp + c + ds[w] == dh[school] || ds[p] + cp + c + dh[w] == dh[school]) {
if (!mrk.count({w, v}) && dist[{w, v}] > dist[{v, p}]) {
dist[{w, v}] = dist[{v, p}];
pq.push({{-dist[{w, v}], -c}, {w, v}});
// printf("updated!\n");
} else {
// printf("not updated\n");
}
}
}
// print_map(dist);
}
vector<int> ret(n + 1, LLINF);
for (auto [k, val]: dist) {
ret[k.first] = min(ret[k.first], val);
}
return ret;
}
void print_dists(vector<int> &v) {
for (int i = 1; i <= n; i++) {
cout << i << " -> " << v[i] << endl;
}
}
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);
// cout << "after dijkstra from house:" << endl;
// print_dists(d_house);
dists[house] = LLINF;
dists[school] = 0;
vector<int> d_school = dijkstra(dists);
// cout << "after dijkstra from school:" << endl;
// print_dists(d_school);
dists[school] = LLINF;
dists[book_u] = 0;
vector<int> step_0 = dijkstra(dists);
// cout << "after dijkstra from book u:" << endl;
// print_dists(step_0);
// inside commuter pass
vector<int> step_1 = commuter_pass(step_0, d_house, d_school, school);
// cout << "after commuter pass:" << endl;
// print_dists(step_1);
// after leaving commuter pass
vector<int> step_2 = dijkstra(step_1);
// cout << "after post-commuter pass dijkstra:" << endl;
// print_dists(step_2);
cout << min({ step_0[book_v], step_1[book_v], step_2[book_v] }) << endl;
}
int32_t main() {
solve();
return 0;
}
