#include<bits/stdc++.h> using namespace std; using i64 = long long; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin >> n >> m; int s,t; cin >> s >> t; int u,v; cin >> u >> v; s --; t --; u --; v --; assert(s == u); vector<vector<pair<int,int>>> adj(n); for(int i = 0;i < m;i++){ int a,b,w; cin >> a >> b >> w; a --; b --; adj[a].push_back({b,w}); adj[b].push_back({a,w}); } const i64 inf = 1e18; function<vector<i64>(int)> f = [&](int src){ priority_queue<pair<i64,int>,vector<pair<i64,int>>,greater<pair<i64,int>>> pq; vector<i64> dist(n,inf); dist[src] = 0LL; pq.push({0LL,src}); while(!pq.empty()){ auto p = pq.top(); pq.pop(); int a = p.second; i64 c = p.first; for(auto pp : adj[a]){ int vv = pp.first; int w = pp.second; if(dist[vv] > c + w){ dist[vv] = c + w; pq.push({c + w,vv}); } } } return dist; }; vector<i64> distx = f(s); vector<i64> disty = f(t); priority_queue<pair<i64,int>,vector<pair<i64,int>>,greater<pair<i64,int>>> pq; vector<i64> dist(n,inf); for(int i = 0;i < n;i++){ if(distx[i] + disty[i] == distx[t]){ pq.push({0LL,i}); dist[i] = 0LL; } } while(!pq.empty()){ auto p = pq.top(); pq.pop(); int a = p.second; i64 c = p.first; for(auto pp : adj[a]){ int vv = pp.first; int w = pp.second; if(dist[vv] > c + w){ dist[vv] = c + w; pq.push({c + w,vv}); } } } cout << dist[v] << '\n'; return 0; }