#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 --; 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; vector<vector<i64>> dist(n,vector<i64>(n,inf)); for(int i = 0;i < n;i++){ dist[i][i] = 0LL; for(auto p : adj[i]){ dist[i][p.first] = min(dist[i][p.first],(i64)p.second); dist[p.first][i] = min(dist[p.first][i],(i64)p.second); } } for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ for(int p = 0;p < n;p++){ dist[j][p] = min(dist[j][p],dist[j][i] + dist[i][p]); } } } vector<int> gd; for(int i = 0;i < n;i++){ if(dist[s][i] + dist[i][t] == dist[s][t]){ gd.push_back(i); } } priority_queue<pair<i64,int>,vector<pair<i64,int>>,greater<pair<i64,int>>> pq; vector<i64> dist2(n,inf); for(int st = 0;st < n;st ++){ for(int i = 0;i < n;i++){ if(dist[s][st] + dist[st][i] + dist[i][t] == dist[s][t]){ dist2[i] = min(dist2[i],dist[u][st]); } if(dist[s][i] + dist[i][st] + dist[st][t] == dist[s][t]){ dist2[i] = min(dist2[i],dist[u][st]); } } } for(int i = 0;i < n;i++){ pq.push({dist2[i],i}); } 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(dist2[vv] > c + w){ dist2[vv] = c + w; pq.push({c + w,vv}); } } } cout << dist2[v] << '\n'; return 0; }