#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1e5+10; int n, m, st, en, U, V; ll dist[4][N], dp1[N], dp2[N], res = 2e18; bool vis[N]; vector<pair<int, int>> adj[N]; inline void dijsktra(int x, int S){ priority_queue<pair<ll, int>, vector<pair<ll, int>>,greater<pair<ll, int>>> pq; memset(dist[x], 0x3f, sizeof dist[x]); pq.push({dist[x][S] = 0, S}); while(!pq.empty()){ auto [d, u] = pq.top(); pq.pop(); if(dist[x][u] < d) continue; for(auto [v, w] : adj[u]){ if(dist[x][v] > d+w){ pq.push({dist[x][v] = d+w, v}); } } } } void dfs(int u){ if(vis[u]) return; vis[u] = 1; dp1[u] = dp2[u] = 2e18; for(auto [v, w] : adj[u]){ if(dist[0][v] + dist[1][v] != dist[0][en] || dist[0][v] < dist[0][u]) continue; dfs(v); dp1[u] = min(dp1[u], dp1[v]); dp2[u] = min(dp2[u], dp2[v]); } res = min({res, dp1[u] + dist[2][u], dp2[u] + dist[3][u]}); dp1[u] = min(dp1[u], dist[3][u]); dp2[u] = min(dp2[u], dist[2][u]); } 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(0, st); dijsktra(1, en); dijsktra(2, U); dijsktra(3, V); dfs(st); cout << min(res, dist[2][V]) << '\n'; }