#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 dij(int a, vi &dist) { vector<bool> vis(n+1); priority_queue<pr> q; q.push({0, a}); dist[a] = 0; while (!q.empty()) { auto [d, u] = q.top(); q.pop(); if (vis[u]) continue; vis[u] = true; for (auto [v, w] : adj[u]) { if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; q.push({-dist[v], v}); } } } } 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}); } vi d1(n+1, 1e18), d2(n+1, 1e18); dij(S, d1); dij(T, d2); vi dist(n+1, 1e18); priority_queue<pr> q; for (int i = 1; i <= n; i++) { if (d1[i] + d2[i] == d1[T]) { q.push({0, i}); dist[i] = 0; } } vector<bool> vis(n+1); 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; }