#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const int MAXN = 1e5 + 5;
ll n, m, A, B, C, D;
vector<pll> adj[MAXN];
vector<ll> parent(MAXN, -1);
vector<ll> dist(MAXN, INF);
set<pair<ll, ll>> used_edges; // Lưu các cạnh thuộc đường buổi sáng
void dijkstra(ll start, ll end) {
fill(dist.begin(), dist.end(), INF);
fill(parent.begin(), parent.end(), -1);
priority_queue<pll, vector<pll>, greater<pll>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (u == end) break;
if (d > dist[u]) continue;
for (auto [v, c] : adj[u]) {
if (dist[v] > dist[u] + c) {
dist[v] = dist[u] + c;
parent[v] = u;
pq.push({dist[v], v});
}
}
}
}
ll find_min_path_with_free_edges() {
vector<ll> new_dist(n + 1, INF);
priority_queue<pll, vector<pll>, greater<pll>> pq;
new_dist[C] = 0;
pq.push({0, C});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (u == D) break;
if (d > new_dist[u]) continue;
for (auto [v, c] : adj[u]) {
// Kiểm tra cạnh (u, v) có free không
bool is_free = used_edges.count({min(u, v), max(u, v)});
ll new_cost = d + (is_free ? 0 : c);
if (new_cost < new_dist[v]) {
new_dist[v] = new_cost;
pq.push({new_dist[v], v});
}
}
}
return new_dist[D];
}
int main() {
freopen("tunnel.inp", "r", stdin);
freopen("tunnel.out", "w", stdout);
cin >> n >> m;
cin >> A >> B >> C >> D;
for (int i = 0; i < m; i++) {
ll u, v, c;
cin >> u >> v >> c;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
// Bước 1: Tìm đường ngắn nhất A → B
dijkstra(A, B);
// Lưu các cạnh thuộc đường buổi sáng
ll current = B;
while (current != A && current != -1) {
ll prev = parent[current];
used_edges.insert({min(prev, current), max(prev, current)});
current = prev;
}
// Bước 2: Tìm đường ngắn nhất C → D với cạnh free
ll result = find_min_path_with_free_edges();
cout << result << endl;
return 0;
}
