#include <bits/stdc++.h> #include <cstdint> #define int long long #define endl "\n" #define pb push_back #define op ios::sync_with_stdio(false); cin.tie(0); #define pii pair<int, int> using namespace std; const int MAXN = 1e6 + 9; const int INF = 1e18 + 9; int n, m, dist[MAXN]; vector <pii> adj[MAXN]; bool visited[MAXN]; void dijkstra(int s){ for(int i = 1; i <= n; i++){ dist[i] = INF; visited[i] = false; } dist[s] = 0; priority_queue <pii, vector<pii>, greater<pii>> fila; fila.push({0, s}); while(!fila.empty()){ int u = fila.top().second; fila.pop(); if(visited[u]) continue; visited[u] = true; for(auto V : adj[u]){ int v = V.first, w = V.second; if(dist[v] > dist[u]+w){ dist[v] = dist[u]+w; fila.push({dist[v], v}); } } } } int32_t main() { op int s, t, u, v; cin >> n >> m >> s >> t >> u >> v; for(int i = 0; i < m; i++){ int a, b, c; cin >> a >> b >> c; adj[a].pb({b, c}); adj[b].pb({a, c}); } dijkstra(u); cout << dist[v] << endl; }