#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define TEST
#define all(x) (x).begin(), (x).end()
const long long INF = 1e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
int S, T;
cin >> S >>T;
int U, V;
cin >> U >> V;
vector<vector< pair<int, long long>>> adj(N+1);
for (int i=1; i<= M; i++) {
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
vector<long long> distU(N+1, INF);
using Type = pair< long long, int>;
priority_queue< Type, vector<Type>, greater<Type>> pq;
distU[U] = 0;
pq.push({0,U});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d> distU[u]) continue;
for (auto [v, len] : adj[u]) {
if (len+distU[u] < distU[v]) {
distU[v] = len+distU[u];
pq.push({distU[v], v});
}
}
}
vector<long long> distV(N+1, INF);
distV[V] = 0;
pq.push({0,V});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d> distV[u]) continue;
for (auto [v, len] : adj[u]) {
if (len+distV[u] < distV[v]) {
distV[v] = len+distV[u];
pq.push({distV[v], v});
}
}
}
vector<long long> distS(N+1, INF);
vector<long long> running_distU(N+1, INF);
vector<long long> running_distV(N+1, INF);
distS[S] = 0;
running_distU[S] = distU[S];
running_distV[S] = distV[S];
pq.push({0,S});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d> distS[u]) continue;
for (auto [v, len] : adj[u]) {
if (len+distS[u] ==distS[v]) {
running_distU[v] = min(running_distU[v] , running_distU[u]);
running_distV[v]= min(running_distV[v] , running_distV[u]);
}
if (len+distS[u] < distS[v]) {
distS[v] = len+distS[u];;;
pq.push({distS[v], v});
running_distU[v] = min(distU[v] , running_distU[u]);
running_distV[v] = min(distV[v] , running_distV[u]);
}
}
}
vector<long long> distT(N+1, INF);
vector<long long> running_distU_fromT(N+1, INF);
vector<long long> running_distV_fromT(N+1, INF);
distT[T] = 0;
running_distU_fromT[T] = distU[T];
running_distV_fromT[T] = distV[T];
vector<vector<int>> prev_node(N+1);
pq.push({0,T});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d> distT[u]) continue;
for (auto [v, len] : adj[u]) {
if (len+distT[u] ==distT[v]) {
running_distU_fromT[v] = min(running_distU_fromT[v] , running_distU_fromT[u]);
running_distV_fromT[v]= min(running_distV_fromT[v] , running_distV_fromT[u]);
prev_node[v].push_back(u);
}
if (len+distT[u] < distT[v]) {
prev_node[v]= {};
prev_node[v].push_back(u);
distT[v] = len+distT[u];
pq.push({distT[v], v});
running_distU_fromT[v] = min(distU[v] , running_distU_fromT[u]);
running_distV_fromT[v] = min(distV[v] , running_distV_fromT[u]);
}
}
}
long long ans = distU[V];
vector<bool> check(N+1, false);
auto graph_algo =[&]( auto&& self, int u)->void {
ans =min( {ans, running_distU_fromT[u] +running_distV[u], running_distV_fromT[u] +running_distU[u]} );
check[u] =true;
for (int v: prev_node[u]) {
if (check[v]) continue;
self(self, v);
}
};
graph_algo(graph_algo,S);
cout << ans << "\n";
return 0;
}
