#include "bits/stdc++.h"
using namespace std;
#define int long long
const int N = 1e6 + 5;
#define II pair<int,int>
#define fi first
#define se second
int n, m, s, t, U, V;
int f[N], f2[N];
vector<II> adj[N], adj2[N];
vector<int> parent[N];
template<class X, class Y> bool mini(X& x, const Y y) {
if (x > y) return x = y, 1;
return 0;
}
// Dijkstra để tìm shortest path từ `node`
void dijkstra(int node) {
memset(f, 0x3f, sizeof f);
priority_queue<II, vector<II>, greater<II>> q;
q.push({0, node});
f[node] = 0;
while (!q.empty()) {
II u = q.top(); q.pop();
if (u.fi != f[u.se]) continue;
for (II v: adj[u.se]) {
if (mini(f[v.se], f[u.se] + v.fi)) {
q.push({f[v.se], v.se});
parent[v.se].clear();
parent[v.se].push_back(u.se);
} else if (f[v.se] == f[u.se] + v.fi) {
parent[v.se].push_back(u.se);
}
}
}
}
// Xây dựng `adj2` với cạnh zero-cost cho đường đi `s → t`
void build_adj2() {
queue<int> q;
vector<bool> visited(n + 1, false);
q.push(t);
visited[t] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : parent[u]) {
adj2[u].push_back({0, v});
adj2[v].push_back({0, u});
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
// Giữ nguyên các cạnh khác nhưng chỉ thêm nếu không thuộc shortest path
for (int i = 1; i <= n; i++) {
for (II j : adj[i]) {
if (f[i] + j.fi != f[j.se]) { // Nếu không phải cạnh của đường đi `s → t`
adj2[i].push_back(j);
}
}
}
}
// Dijkstra tìm đường từ `U` đến `V` trên `adj2`
void dijkstra2(int node) {
memset(f2, 0x3f, sizeof f2);
priority_queue<II, vector<II>, greater<II>> q;
q.push({0, node});
f2[node] = 0;
while (!q.empty()) {
II u = q.top(); q.pop();
if (u.fi != f2[u.se]) continue;
for (II v: adj2[u.se]) {
if (mini(f2[v.se], f2[u.se] + v.fi)) {
q.push({f2[v.se], v.se});
}
}
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen("_ab.inp", "r")) {
freopen("_ab.inp", "r", stdin);
freopen("_ab.out", "w", stdout);
}
cin >> n >> m;
cin >> s >> t >> U >> V;
for (int i = 1; i <= m; i++) {
int u, v, c;
cin >> u >> v >> c;
adj[u].push_back({c, v});
adj[v].push_back({c, u});
}
dijkstra(s); // Tìm shortest path từ `s` đến `t`
build_adj2(); // Xây dựng `adj2` với cạnh zero-cost
dijkstra2(U); // Tìm đường từ `U` đến `V` trên đồ thị mới
cout << f2[V] << "\n";
}
