#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;
int s, t, U, V;
int du[N], dv[N], ds[N];
int dp[2][N];
int ans;
bool visited[N];
vector<II> adj[N];
template<class X, class Y> bool mini(X& x, const Y y) {
if (x > y) return x = y, 1;
return 0;
}
// Standard Dijkstra to compute shortest paths from start to all other nodes
void dijkstra1(int start, int dist[]) {
memset(visited, false, sizeof(visited));
priority_queue<II, vector<II>, greater<II>> q;
q.push({0, start});
while (!q.empty()) {
int cost = q.top().fi;
int node = q.top().se;
q.pop();
if (!visited[node]) {
dist[node] = cost;
visited[node] = true;
for (II edge : adj[node]) {
int next_node = edge.se;
int next_cost = edge.fi;
q.push({cost + next_cost, next_node});
}
}
}
}
// Modified Dijkstra to find optimal path considering commuter pass
void dijkstra2(int start, int end) {
// Initialize dp arrays
for (int i = 0; i <= n; i++) {
dp[0][i] = LLONG_MAX / 2;
dp[1][i] = LLONG_MAX / 2;
}
memset(visited, false, sizeof(visited));
priority_queue<pair<int, II>, vector<pair<int, II>>, greater<pair<int, II>>> q;
q.push({0, {start, 0}});
dp[0][0] = dp[1][0] = LLONG_MAX / 2;
while (!q.empty()) {
int cost = q.top().fi;
int node = q.top().se.fi;
int parent = q.top().se.se;
q.pop();
if (!visited[node]) {
visited[node] = true;
ds[node] = cost;
// Update dp values - minimum cost to reach U and V from current node
dp[0][node] = min(du[node], dp[0][parent]);
dp[1][node] = min(dv[node], dp[1][parent]);
for (II edge : adj[node]) {
int next_node = edge.se;
int next_cost = edge.fi;
q.push({cost + next_cost, {next_node, node}});
}
}
else if (cost == ds[node]) {
// If we found another path with same cost, check if it's better for U-V
int new_cost_u = min(du[node], dp[0][parent]);
int new_cost_v = min(dv[node], dp[1][parent]);
if (new_cost_u + new_cost_v <= dp[0][node] + dp[1][node]) {
dp[0][node] = new_cost_u;
dp[1][node] = new_cost_v;
}
}
}
// Update the answer with the cost at the end node
ans = min(ans, dp[0][end] + dp[1][end]);
}
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 a, b, c;
cin >> a >> b >> c;
adj[a].push_back({c, b});
adj[b].push_back({c, a});
}
// Find shortest paths from U and V to all other nodes
dijkstra1(U, du);
dijkstra1(V, dv);
// Set initial answer to the direct distance from U to V
ans = du[V];
// Try both directions for the commuter pass
dijkstra2(s, t);
dijkstra2(t, s);
cout << ans;
return 0;
}
