#include<bits/stdc++.h>
#define bl bool
#define db double
#define fl float
#define st string
#define pb push_back
#define pf push_front
#define is insert
#define endl "\n"
#define pba pop_back
#define pfr pop_front
#define ub upper_bound
#define lb lower_bound
#define fi first
#define se second
#define FOR(i, l, r, st) for(int i = l; i <= r; i += st)
#define FOS(i, l, r, sl) for(int i = l; i >= r; i -= sl)
#define mii map<int, int>
#define us unordered_set
#define pii pair<int, int>
#define vt vector
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int INF = 1e18;
void suncuti() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
int n, m, A, B, C, D;
vt<pii> kt[maxn]; // đồ thị ban đầu
map<pii, int> isVIP; // đánh dấu cạnh VIP
int trace[maxn];
int dp[maxn];
// Dijkstra để tìm đường từ A đến B
void dijkstra_AB() {
fill(dp, dp + n + 1, INF);
memset(trace, -1, sizeof(trace));
dp[A] = 0;
priority_queue<pii, vt<pii>, greater<pii>> q;
q.push({0, A});
while (!q.empty()) {
int du = q.top().fi;
int u = q.top().se;
q.pop();
if (du > dp[u]) continue;
for (auto v : kt[u]) {
int cost = v.se + dp[u];
if (cost < dp[v.fi]) {
dp[v.fi] = cost;
trace[v.fi] = u;
q.push({dp[v.fi], v.fi});
}
}
}
// truy vết từ B ngược về A để đánh dấu cạnh VIP
int u = B;
while (trace[u] != -1) {
int p = trace[u];
isVIP[{u, p}] = 1;
isVIP[{p, u}] = 1;
u = p;
}
}
// Dijkstra từ C đến D, với VIP = miễn phí
int dijkstra_CD() {
fill(dp, dp + n + 1, INF);
dp[C] = 0;
priority_queue<pii, vt<pii>, greater<pii>> q;
q.push({0, C});
while (!q.empty()) {
int du = q.top().fi;
int u = q.top().se;
q.pop();
if (du > dp[u]) continue;
for (auto v : kt[u]) {
int w = isVIP[{u, v.fi}] ? 0 : v.se;
if (dp[u] + w < dp[v.fi]) {
dp[v.fi] = dp[u] + w;
q.push({dp[v.fi], v.fi});
}
}
}
return dp[D];
}
main() {
suncuti();
cin >> n >> m;
cin >> A >> B;
cin >> C >> D;
FOR(i, 1, m, 1) {
int u, v, w;
cin >> u >> v >> w;
kt[u].pb({v, w});
kt[v].pb({u, w});
}
dijkstra_AB(); // bước 1: tìm tuyến VIP
cout << dijkstra_CD(); // bước 2: tìm đường từ C → D với VIP miễn phí
}
