#include <bits/stdc++.h> using namespace std; typedef long long ll; int N; vector<pair<int,ll>> g[100001]; ll dist[100001]; bool vis[100001]; vector<int> par[100001]; void dijkstra(vector<int> src) { for (int u = 1; u <= N; u++) vis[u] = false, dist[u] = LLONG_MAX; priority_queue<pair<ll, int>> pq; for (int u : src) { dist[u] = 0; pq.push({0LL, u}); } while (!pq.empty()) { int u = pq.top().second; pq.pop(); vis[u] = true; for (auto [v, l] : g[u]) if (dist[v] > dist[u] + l) { par[v] = {u}; dist[v] = dist[u] + l; pq.push({-dist[v], v}); } else if (dist[v] == dist[u] + l) par[v].push_back(u); while (!pq.empty() && vis[pq.top().second]) pq.pop(); } } vector<int> path; void dfs(int u) { vis[u] = true; path.push_back(u); for (int v : par[u]) if (!vis[v]) dfs(v); } int main() { int M, S, T, U, V; cin >> N >> M >> S >> T >> U >> V; for (int i = 0, a, b; i < M; i++) { ll c; cin >> a >> b >> c; g[a].push_back({b, c}); g[b].push_back({a, c}); } dijkstra({S}); memset(vis, false, sizeof(vis)); dfs(T); dijkstra(path); cout << dist[U] + dist[S] << '\n'; return 0; }