#include<bits/stdc++.h> #define int long long using namespace std; vector<pair<int, int>> ad[400005]; vector<int> optimal[400005]; int dis[400005]; bool visited[400005]; void dijkstra(int s) { memset(dis, 0x3f, sizeof(dis)); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> w; dis[s] = 0; w.push({0, s}); while(w.size() > 0){ int u = w.top().second, d = w.top().first; w.pop(); if(dis[u] != d) continue; for(pair<int, int> i : ad[u]){ int v = i.first, c = i.second; if(dis[v] > d+c){ optimal[v].clear(); w.push({d+c, v}); } if(dis[v] >= d+c){ dis[v] = d+c; optimal[v].push_back(u); } } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m, s, t, ss, tt; cin>>n>>m>>s>>t>>ss>>tt; vector<pair<pair<int, int>, int>> edges; for(int i = 1; i <= m; i++){ int u, v, c; cin>>u>>v>>c; ad[u].push_back({v, c}); ad[v].push_back({u, c}); edges.push_back({{u, v}, c}); edges.push_back({{v, u}, c}); } dijkstra(s); //Some traceback queue<int> w; w.push(t); visited[t] = 1; while(w.size() > 0){ int u = w.front(); w.pop(); for(int v : optimal[u]) if(visited[v] == 0){ w.push(v); visited[v] = 1; } } for(int i = 1; i <= n; i++) if(visited[i] == 0) dis[i] = -1e18; for(int i = 1; i <= n; i++){ad[i].clear(); optimal[i].clear();} for(auto i : edges){ int u = i.first.first, v = i.first.second, c = i.second; if(dis[v] == dis[u] + c){ //cerr<<"A"<<u<<" "<<v<<endl; ad[u].push_back({v+n, 0}); ad[u+n].push_back({v+n, 0}); } else if(dis[u] == dis[v]+c){ ad[u].push_back({v+2*n, 0}); ad[u+2*n].push_back({v+2*n, 0}); } ad[u].push_back({v, c}); ad[u+n].push_back({v+3*n, c}); ad[u+2*n].push_back({v+3*n, c}); ad[u+3*n].push_back({v+3*n, c}); } dijkstra(ss); cout<<min({dis[tt], dis[tt+n], dis[tt+n+n], dis[tt+n+n+n]}); }