#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1e5+10; int n, m, st, en, U, V; ll dist1[N], dist2[N], dist3[2][N]; vector<pair<int, int>> adj[N]; inline void dijsktra(){ priority_queue<pair<ll, int>, vector<pair<ll, int>>,greater<pair<ll, int>>> pq; memset(dist1, 0x3f, sizeof dist1); memset(dist2, 0x3f, sizeof dist2); pq.push({dist1[st] = 0, st}); while(!pq.empty()){ auto [d, u] = pq.top(); pq.pop(); if(dist1[u] < d) continue; for(auto [v, w] : adj[u]){ if(dist1[v] > d+w){ pq.push({dist1[v] = d+w, v}); } } } pq.push({dist2[en] = 0, en}); while(!pq.empty()){ auto [d, u] = pq.top(); pq.pop(); if(dist2[u] < d) continue; for(auto [v, w] : adj[u]){ if(dist2[v] > d+w){ pq.push({dist2[v] = d+w, v}); } } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> st >> en >> U >> V; while(m--){ int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } dijsktra(); const ll mn = dist1[en]; memset(dist3, 0x3f, sizeof dist3); //cost, node, in_node, in(bool), dist, prev, already priority_queue<tuple<ll, int, int, bool, ll, int, bool>, vector<tuple<ll, int, int, bool, ll, int, bool>>, greater<tuple<ll, int, int, bool, ll, int, bool>>> pq; pq.push({dist3[0][U] = 0, U, -1, false, 0, -1, false}); if(dist1[U] + dist2[U] == mn) pq.push({dist3[1][U] = 0, U, U, true, 0, -1, true}); while(!pq.empty()){ auto [c, u, in_node, in, d, prev, already] = pq.top(); pq.pop(); if(dist3[in][u] < c) continue; if(in){ for(auto [v, w] : adj[u]){ if(v == prev) continue; if(d+w == mn - dist1[v] - dist2[in_node] || d+w == mn - dist1[in_node] - dist2[v]){ if(dist3[1][v] > c) pq.push({dist3[1][v] = c, v, in_node, true, d+w, u, true}); } if(dist3[0][v] > c+w) pq.push({dist3[0][v] = c+w, v, -1, false, 0, u, true}); } }else{ for(auto [v, w] : adj[u]){ if(v == prev) continue; if(dist1[v]+dist2[v] == mn && (!already)){ if(dist3[1][v] > c+w) pq.push({dist3[1][v] = c+w, v, v, true, 0, u, true}); } if(dist3[0][v] > c+w) pq.push({dist3[0][v] = c+w, v, -1, false, 0, u, already}); } } } cout << min(dist3[0][V], dist3[1][V]) << '\n'; }