#include <bits/stdc++.h> using namespace std; #define pb push_back #define int long long const int MOD = 1e9 + 7; const int INF = 1e15; const int N = 1e6; int n, m, k, a, b, c, d, h, l, r, q, u, v, x, y; vector<int> arr(N); vector<int> adj[N]; vector<int> vis(N); map<pair<int, int>, int> weight; int s, t; void solve() { cin >> n >> m; cin >> s >> t; cin >> u >> v; for(int i = 1; i<=m; i++) { cin >> a >> b >> c; adj[a].pb(b); adj[b].pb(a); weight[{a, b}] = c; weight[{b, a}] = c; } vector<int> dist(n+1, INF); vector<int> parent(n+1); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que; dist[s] = 0; que.push({0, s}); while(!que.empty()) { int d = que.top().first; int a = que.top().second; que.pop(); if(d > dist[a]) continue; for(auto b : adj[a]) { if(dist[a] + weight[{b, a}] < dist[b]) { dist[b] = dist[a] + weight[{a, b}]; que.push({dist[b], b}); parent[b] = a; } } } r = t; while(r != s) { weight[{r, parent[r]}] = 0; weight[{parent[r], r}] = 0; r = parent[r]; } for(int j = 0; j<=n; j++) { parent[j] = 0; dist[j] = INF; } dist[v] = 0; que.push({0, v}); while(!que.empty()) { int d = que.top().first; int a = que.top().second; que.pop(); if(d > dist[a]) continue; for(auto b : adj[a]) { if(dist[a] + weight[{b, a}] < dist[b]) { dist[b] = dist[a] + weight[{a, b}]; que.push({dist[b], b}); parent[b] = a; } } } // for(auto j : weight) cout << j.first.first << " " << j.first.second << " " << j.second << "\n"; // for(auto j : parent) cout << j << " "; r = u; c = 0; while(r != v) { c += weight[{r, parent[r]}]; r = parent[r]; } cout << c; } int32_t main() { ios::sync_with_stdio(false); cout.tie(0); cin.tie(0); int tc = 1; // cin >> tc; while(tc--) { solve(); cout << "\n"; } return 0; }