// TranThienPhuc2657
// 2 ngay truoc khi toi ki thi Hoc sinh gioi quoc gia 2025 - 2026, 25/12/2025.
#include <bits/stdc++.h>
using namespace std;
#define file "TASK"
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define Sz(x) ((int) (x).size())
#define getBit(mask, i) (((mask) >> (i)) & 1)
template <typename T1, typename T2> bool mini(T1 &A, T2 B) {if (A > B) A = B; else return 0; return 1;}
template <typename T1, typename T2> bool maxi(T1 &A, T2 B) {if (A < B) A = B; else return 0; return 1;}
const int inf = 2e9 + 7;
const ll linf = 1e18l + 7;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
int n, m, A, B, C, D;
struct Edge {
int u, v, w;
int other(int x) {
return u ^ v ^ x;
}
};
vector <Edge> edges;
vector <int> adj[N];
ll dA[N], dB[N];
ll d[4][N];
struct Dijkstra_state {
int ty, u;
ll du;
bool operator < (const Dijkstra_state &ot) const {
return du > ot.du;
}
};
ll res = linf;
// inp
void inp() {
cin >> n >> m;
cin >> A >> B >> C >> D;
edges.pb({0, 0, 0});
for (int i = 1; i <= m; i++) {
int u, v, w; cin >> u >> v >> w;
edges.pb({u, v, w});
adj[u].pb(i);
adj[v].pb(i);
}
}
// init
void init() {
}
// proc
bool inSP(int u, int v, int w) {
return ((dA[u] + w) == dA[v] and (dA[u] + dB[v] + w) == dA[B]);
}
void dijkstra(int s, ll d[]) {
for (int u = 1; u <= n; u++) d[u] = linf;
priority_queue <pll, vector <pll>, greater <pll>> pq;
d[s] = 0; pq.push({d[s], s});
while (!pq.empty()) {
int u = pq.top().se; ll du = pq.top().fi; pq.pop();
if (du > d[u]) continue;
for (int idE: adj[u]) {
int v = edges[idE].other(u), w = edges[idE].w;
if (mini(d[v], d[u] + w)) pq.push({d[v], v});
}
}
}
void dijkstra2(int s) {
for (int u = 1; u <= n; u++) d[0][u] = d[1][u] = d[2][u] = linf;
priority_queue <Dijkstra_state> pq;
d[0][s] = 0; pq.push({0, s, d[0][s]});
while (!pq.empty()) {
int ty = pq.top().ty, u = pq.top().u; ll du = pq.top().du; pq.pop();
if (du > d[ty][u]) continue;
for (int idE: adj[u]) {
int v = edges[idE].other(u), w = edges[idE].w;
if (ty == 0) {
if (mini(d[0][v], d[0][u] + w)) pq.push({0, v, d[0][v]});
if (inSP(u, v, w) and mini(d[1][v], d[0][u])) pq.push({1, v, d[1][v]});
}
else if (ty == 1) {
if (inSP(u, v, w) and mini(d[1][v], d[1][u])) pq.push({1, v, d[1][v]});
if (mini(d[2][v], d[1][u] + w)) pq.push({2, v, d[2][v]});
}
else {
if (mini(d[2][v], d[2][u] + w)) pq.push({2, v, d[2][v]});
}
}
}
}
void proc() {
dijkstra(A, dA);
dijkstra(B, dB);
dijkstra2(C);
mini(res, min({d[0][D], d[1][D], d[2][D]}));
dijkstra2(D);
mini(res, min({d[0][C], d[1][C], d[2][C]}));
cout << res;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(file".inp", "r")) {
freopen(file".inp", "r", stdin);
freopen(file".out", "w", stdout);
}
inp();
init();
proc();
cerr << "Time elapsed: " << TIME << "s.\n";
return 0;
}
