#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
const ll INF = 1e18;
int main() {
int n, m;
cin >> n >> m;
int s, t;
cin >> s >> t;
int u, v;
cin >> u >> v;
// Adjacency list to store the graph
vector<vector<pair<int, ll>>> graph(n + 1);
// Store all railways
vector<tuple<int, int, ll>> railways(m);
for (int i = 0; i < m; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
// Store the railway
railways[i] = {a, b, c};
// Add edges to the graph
graph[a].push_back({b, c});
graph[b].push_back({a, c});
}
// Dijkstra's algorithm to find shortest path from a given source
auto dijkstra = [&](int source, vector<ll>& dist) {
dist.assign(n + 1, INF);
priority_queue<pli, vector<pli>, greater<pli>> pq;
dist[source] = 0;
pq.push({0, source});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto& [v, w] : graph[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
};
// Find shortest path from S to T in the original graph
vector<ll> dist_s_to_all;
dijkstra(s, dist_s_to_all);
ll original_cost_s_to_t = dist_s_to_all[t];
// For each valid S-T path, check the cost from U to V
ll min_cost_u_to_v = INF;
// Brute force through all possible paths from S to T
// In a real implementation, we would optimize this further
// Approach: Try all possible edges that could be part of commuter pass
// For each possible set, compute the min cost from U to V
// For simplicity, let's try a clever approach:
// 1. Create a new graph where railways in S-T path have cost 0
// 2. Find shortest path from U to V in this new graph
// Find the original shortest path from S to T
vector<int> parent(n + 1, -1);
vector<bool> is_on_st_path(m, false);
// Re-run Dijkstra from S to T to get the path
priority_queue<pli, vector<pli>, greater<pli>> pq;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (u == t) break;
for (auto& [v, w] : graph[u]) {
if (dist_s_to_all[u] + w == dist_s_to_all[v]) {
parent[v] = u;
pq.push({dist_s_to_all[v], v});
break;
}
}
}
// Mark edges on S-T path
int curr = t;
while (curr != s && parent[curr] != -1) {
int prev = parent[curr];
for (int i = 0; i < m; i++) {
auto [a, b, c] = railways[i];
if ((a == prev && b == curr) || (a == curr && b == prev)) {
is_on_st_path[i] = true;
break;
}
}
curr = prev;
}
// Create a modified graph for U to V path
vector<vector<pair<int, ll>>> modified_graph(n + 1);
for (int i = 0; i < m; i++) {
auto [a, b, c] = railways[i];
ll new_cost = is_on_st_path[i] ? 0 : c;
modified_graph[a].push_back({b, new_cost});
modified_graph[b].push_back({a, new_cost});
}
// Find shortest path from U to V in the modified graph
vector<ll> dist_u_to_all(n + 1, INF);
dist_u_to_all[u] = 0;
priority_queue<pli, vector<pli>, greater<pli>> pq2;
pq2.push({0, u});
while (!pq2.empty()) {
auto [d, node] = pq2.top();
pq2.pop();
if (d > dist_u_to_all[node]) continue;
for (auto& [next, weight] : modified_graph[node]) {
if (dist_u_to_all[node] + weight < dist_u_to_all[next]) {
dist_u_to_all[next] = dist_u_to_all[node] + weight;
pq2.push({dist_u_to_all[next], next});
}
}
}
cout << dist_u_to_all[v] << endl;
return 0;
}
