#include <bits/stdc++.h> using namespace std; using ll = long long; #define vi vector<long long> #define all(x) x.begin(), x.end() #define endl "\n" #define pr pair<ll, ll> #define ff first #define ss second void solution(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); solution(); return 0; } const int N = 1e5+10; ll n, m, S, T, U, V; vector<pr> adj[N]; void solution() { cin >> n >> m >> S >> T >> U >> V; while (m--) { ll a, b, w; cin >> a >> b >> w; adj[a].push_back({b, w}); adj[b].push_back({a, w}); } priority_queue<pr> q; vi prt(n+1); vi dist(n+1, 1e18); vector<bool> vis(n+1); q.push({0, S}); dist[1] = 0; while (!q.empty()) { auto [d, a] = q.top(); q.pop(); if (a == T) break; if (vis[a]) continue; vis[a] = true; for (auto [b, w] : adj[a]) { if (dist[b] > dist[a] + w) { dist[b] = dist[a] + w; q.push({-dist[b], b}); prt[b] = a; } } } while (!q.empty()) q.pop(); fill(all(vis), 0); vi path; ll c = T; while (c != 0) { int t = c; path.push_back(c); c = prt[c]; for (int i = 0; i < adj[c].size(); i++){ if (adj[c][i].ff == t) { adj[c][i].ss = 0; } } } fill(all(dist), 1e18); for (auto val : path) { q.push({0, val}); dist[val] = 0; } q.push({0, U}); dist[U] = 0; while (!q.empty()) { auto [d, a] = q.top(); q.pop(); if (vis[a]) continue; vis[a] = true; for (auto [b, w] : adj[a]) { if (dist[b] > dist[a] + w) { dist[b] = dist[a] + w; q.push({-dist[b], b}); } } } cout << dist[V] << endl; }