///TRAN THAI BAO :3 #include <iostream> #include <cstdio> #include <vector> #include <queue> using namespace std; #define maxN 100007 #define oo 1e18 typedef pair<long long, long long> pii; typedef pair<pii, long long> piii; int n, m; priority_queue<pii, vector<pii>, greater<pii> >pq; priority_queue<piii, vector<piii>, greater<piii> >pq2; vector<pii>orgAdj[maxN]; vector<piii>adj[maxN][4]; bool vis[maxN] = {false}; int S, T, X, Y; long long orgMinD[maxN]; long long minD[maxN][4]; pii pre[maxN] = {{0, 0}}; void readData() { cin >> n >> m >> S >> T >> X >> Y; int u, v, w; for(int i = 0; i < m; i++) { cin >> u >> v >> w; orgAdj[u].push_back({v, w}); orgAdj[v].push_back({u, w}); adj[u][0].push_back({{v, w}, 0}); adj[v][0].push_back({{u, w}, 0}); adj[u][3].push_back({{v, w}, 3}); adj[v][3].push_back({{u, w}, 3}); } } void dfsPre(int u) { vis[u] = true; int v; long long w; for(int i = 0; i < orgAdj[u].size(); i++) { v = orgAdj[u][i].first; w = orgAdj[u][i].second; if(orgMinD[v] + w == orgMinD[u]) { adj[v][1].push_back({{u, 0}, 1}); adj[u][2].push_back({{v, 0}, 2}); if(!vis[v]) dfsPre(v); } } } void dijkstra() { for(int i = 1; i <= n; i++) orgMinD[i] = oo; orgMinD[S] = 0; pq.push({orgMinD[S], S}); while(!pq.empty()) { int cur = pq.top().second; long long w = pq.top().first; pq.pop(); if(orgMinD[cur] != w) continue; for(int i = 0; i < orgAdj[cur].size(); i++) { w = orgAdj[cur][i].second; int v = orgAdj[cur][i].first; if(orgMinD[v] > orgMinD[cur] + w) { orgMinD[v] = orgMinD[cur] + w; pq.push({orgMinD[v], v}); } } } dfsPre(T); for(int i = 1; i <= n; i++) { adj[i][0].push_back({{i, 0}, 1}); adj[i][0].push_back({{i, 0}, 2}); adj[i][1].push_back({{i, 0}, 3}); adj[i][2].push_back({{i, 0}, 3}); } } void solve() { for(int i = 1; i <= n; i++) { minD[i][0] = oo; minD[i][1] = oo; minD[i][2] = oo; minD[i][3] = oo; } minD[X][0] = 0; pq2.push({{minD[X][0], X}, 0}); while(!pq2.empty()) { int layer = pq2.top().second; int cur = pq2.top().first.second; long long w = pq2.top().first.first; pq2.pop(); if(minD[cur][layer] != w) continue; for(int i = 0; i < adj[cur][layer].size(); i++) { int v = adj[cur][layer][i].first.first; w =adj[cur][layer][i].first.second; int vLay = adj[cur][layer][i].second; if(minD[v][vLay] > minD[cur][layer] + w) { minD[v][vLay] = minD[cur][layer]+w; pq2.push({{minD[v][vLay], v}, vLay}); } } } cout << minD[Y][3]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); readData(); dijkstra(); solve(); return 0; }