#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = LLONG_MAX / 2; // Safe large value to avoid overflow
constexpr int MAXN = 100001;
vector<pair<ll, ll>> graph[MAXN]; // graph[u] = list of (neighbor, cost)
ll distU[MAXN], distV[MAXN], distS[MAXN]; // Shortest distances from U, V, and S
ll dp[2][MAXN]; // dp[0][i] = min distU on path to i, dp[1][i] = min distV
bool visited[MAXN];
ll answer; // Final answer: minimum cost from U to V
// Regular Dijkstra to compute shortest distances from one source
void dijkstra(ll start, ll dist[]) {
fill(dist, dist + MAXN, INF);
fill(visited, visited + MAXN, false);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq;
pq.push({0, start});
dist[start] = 0;
while (!pq.empty()) {
auto [cost, node] = pq.top(); pq.pop();
if (visited[node]) continue;
visited[node] = true;
for (auto [neighbor, edgeCost] : graph[node]) {
if (dist[neighbor] > dist[node] + edgeCost) {
dist[neighbor] = dist[node] + edgeCost;
pq.push({dist[neighbor], neighbor});
}
}
}
}
// Modified Dijkstra to traverse a shortest path tree from S to T
// For each node on shortest S→T path, track min distU and distV
void dijkstraOnShortestPathTree(ll source, ll target) {
fill(distS, distS + MAXN, INF);
fill(dp[0], dp[0] + MAXN, INF);
fill(dp[1], dp[1] + MAXN, INF);
fill(visited, visited + MAXN, false);
priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>, greater<>> pq;
pq.push({0, source, -1}); // (cost, currentNode, parentNode)
distS[source] = 0;
while (!pq.empty()) {
auto [cost, node, parent] = pq.top(); pq.pop();
if (visited[node]) continue;
visited[node] = true;
// Update dp for current node based on its parent
if (parent != -1) {
dp[0][node] = min(distU[node], dp[0][parent]);
dp[1][node] = min(distV[node], dp[1][parent]);
} else {
dp[0][node] = distU[node];
dp[1][node] = distV[node];
}
for (auto [neighbor, edgeCost] : graph[node]) {
if (distS[neighbor] > distS[node] + edgeCost) {
distS[neighbor] = distS[node] + edgeCost;
pq.push({distS[neighbor], neighbor, node});
}
}
}
// If this S-T path has total cost equal to shortest S-T path
// Then consider its use to minimize U-V cost
answer = min(answer, dp[0][target] + dp[1][target]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
for (int i = 0; i < m; ++i) {
ll a, b, c;
cin >> a >> b >> c;
graph[a].emplace_back(b, c);
graph[b].emplace_back(a, c);
}
// Compute shortest paths from U, V, and S
dijkstra(u, distU);
dijkstra(v, distV);
// Initialize answer with the full cost U→V without any commuter pass
answer = distU[v];
// Evaluate both S→T and T→S as possible commuter pass paths
dijkstraOnShortestPathTree(s, t);
dijkstraOnShortestPathTree(t, s);
cout << answer << '\n';
return 0;
}
