#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(int s) {
priority_queue<pii> pq;
vector<int> dist(n + 1, LLINF);
vector<int> mrk(n + 1, false);
pq.push({-0, s});
dist[s] = 0;
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;
}
int commuter_pass(int bu, int bv, int s, int t, vector<int> &dh, vector<int> &ds) {
priority_queue<pip> pq;
// 0 -- nao entrou; 1 -- dentro; 2 -- ja saiu
vector<vector<int>> dist(3);
vector<vector<bool>> mrk(3);
for (int i = 0; i < 3; i++) {
dist[i].clear(); mrk[i].clear();
for (int j = 0; j <= n; j++) {
dist[i].push_back(LLINF);
mrk[i].push_back(false);
}
}
// cerr << "done initializing" << endl;
dist[0][bu] = 0;
if (dh[bu] + ds[bu] == dh[t]) {
dist[1][bu] = 0;
pq.push({-0, {1, bu}});
}
dist[2][bu] = 0;
pq.push({-0, {0, bu}});
pq.push({-0, {2, bu}});
while (!pq.empty()) {
int k = pq.top().second.first;
int v = pq.top().second.second;
pq.pop();
if (mrk[k][v]) continue;
mrk[k][v] = true;
bool v_in_pass = (dh[v] + ds[v] == dh[t]);
for (auto [w, c]: adj[v]) {
// caso em que nao uso commuter pass nessa aresta
if (!mrk[k][w] && dist[k][w] > dist[k][v] + c) {
dist[k][w] = dist[k][v] + c;
pq.push({-dist[k][w], {k, w}});
}
bool w_in_pass = (dh[w] + ds[w] == dh[t]);
// cerr << "checking if " << w << " is in path: " << w_in_pass << endl;
// entrando no commuter pass agora
if (k == 0 && w_in_pass) {
if (!mrk[1][w] && dist[1][w] > dist[0][v] + c) {
dist[1][w] = dist[0][v] + c;
pq.push({-dist[1][w], {1, w}});
}
}
// dentro do commuter pass
if (k == 1) {
// saindo agora
if (!mrk[2][w] && dist[2][w] > dist[1][v] + c) {
dist[2][w] = dist[1][v] + c;
pq.push({-dist[2][w], {2, w}});
}
bool same_path = (dh[v] + ds[w] + c == dh[t] || dh[w] + ds[v] + c == dh[t]);
// cerr << "checking if " << v << " and " << w << " on same path: " << same_path << endl;
// free ride!
if (v_in_pass && w_in_pass && same_path) {
if (!mrk[1][w] && dist[1][w] > dist[1][v]) {
dist[1][w] = dist[1][v];
pq.push({-dist[1][w], {1, w}});
}
}
}
}
}
// for (int k = 0; k < 3; k++) {
// cout << "STEP " << k << endl;
// for (int i = 1; i <= n; i++) {
// cout << "dist[" << i << "] = " << dist[k][i] << endl;
// }
// }
return min({ dist[0][bv], dist[1][bv], dist[2][bv] });
}
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});
}
cerr << "hello world" << endl;
vector<int> d_house = dijkstra(house);
cerr << "done first dijkstra" << endl;
vector<int> d_school = dijkstra(school);
cerr << "done second dijkstra" << endl;
cout << commuter_pass(book_u, book_v, house, school, d_house, d_school) << endl;
}
int32_t main() {
solve();
return 0;
}
