#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]; #define arr array<ll, 3> 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<arr> q; vi prt(n+1); vi dist(n+1, 1e18); vector<bool> vis(n+1); q.push({0, S, 0}); dist[S] = 0; while (!q.empty()) { auto [d, a, p] = q.top(); q.pop(); prt[a] = p; 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, a}); } } } while (!q.empty()) q.pop(); ll c = T; while (c != 0) { int t = 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(vis), 0); fill(all(dist), 1e18); q.push({0, U, 0}); dist[U] = 0; while (!q.empty()) { auto [d, a, p] = 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, 0}); } } } cout << dist[V] << endl; }