#include <iostream>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
struct arbore {
long long nod, cost;
bool operator>(arbore other) const {
return cost > other.cost;
}
};
struct arbore2 {
long long nod, cost, stare;
};
long long n, m, u, v, s, t;
long long rez = 1e18;
vector<vector<arbore>> tabel;
vector<vector<long long>> drumuri;
vector<long long> d;
void dij(long long start) {
priority_queue<arbore, vector<arbore>, greater<arbore>> pq;
d[start] = 0;
pq.push({start, 0});
while (!pq.empty()) {
arbore curent = pq.top();
pq.pop();
if (d[curent.nod] < curent.cost)
continue;
for (auto i : tabel[curent.nod]) {
if (d[i.nod] > curent.cost + i.cost) {
d[i.nod] = curent.cost + i.cost;
pq.push({i.nod, d[i.nod]});
}
}
}
}
void rec(long long start, long long sf) {
queue<arbore2> q;
long long mx = 0;
drumuri[0].push_back(start);
q.push({start, d[start], 0});
while (!q.empty()) {
arbore2 curent = q.front();
q.pop();
if (curent.nod == sf)
continue;
long long cnt = 0;
for (auto i : tabel[curent.nod]) {
if (d[i.nod] == curent.cost - i.cost) {
if (cnt == 0) {
drumuri[curent.stare].push_back(i.nod);
q.push({i.nod, d[i.nod], curent.stare});
cnt++;
mx = max(mx, curent.stare);
} else {
long long nou = mx + 1;
drumuri[nou] = drumuri[curent.stare];
drumuri[nou].push_back(i.nod);
cnt++;
q.push({i.nod, d[i.nod], nou});
mx = max(mx, nou);
}
}
}
}
}
void calc(vector<vector<arbore>>& tabel2) {
priority_queue<arbore, vector<arbore>, greater<arbore>> pq;
vector<long long> di(n + 1, 1e18);
pq.push({u, 0});
di[u] = 0;
while (!pq.empty()) {
arbore curent = pq.top();
pq.pop();
if (di[curent.nod] < curent.cost)
continue;
for (auto i : tabel2[curent.nod]) {
if (di[i.nod] > curent.cost + i.cost) {
di[i.nod] = curent.cost + i.cost;
pq.push({i.nod, di[i.nod]});
}
}
}
rez = min(rez, di[v]);
}
int main() {
cin >> n >> m >> s >> t >> u >> v;
tabel.resize(n + 1);
d.resize(n + 1, 1e18);
drumuri.resize(n + 1);
for (long long i = 1; i <= m; i++) {
long long a, b, c;
cin >> a >> b >> c;
tabel[a].push_back({b, c});
tabel[b].push_back({a, c});
}
// Step 1: Dijkstra from S to T
dij(s);
// Step 2: Reconstruct the shortest path
rec(t, s);
// Step 3: Calculate minimal cost from U to V
for (long long i = 0; i < drumuri.size(); i++) {
if (drumuri[i].size() == 0)
break;
vector<vector<arbore>> nou = tabel;
// Mark the edges in the shortest path as 0 cost
for (long long j = 0; j < drumuri[i].size() - 1; j++) {
long long a = drumuri[i][j], b = drumuri[i][j + 1];
for (auto& edge : nou[a]) {
if (edge.nod == b)
edge.cost = 0;
}
for (auto& edge : nou[b]) {
if (edge.nod == a)
edge.cost = 0;
}
}
// Recalculate the minimal cost from U to V
calc(nou);
}
cout << rez << endl;
return 0;
}
