#include <bits/stdc++.h> using namespace std; vector<vector<pair<int64_t, int64_t>>> graf; vector<pair<pair<int64_t, int64_t>, int64_t>> kraw; vector<int64_t> odl_s, odl_t; void dijkstra(int64_t v, vector<int64_t> &vec){ priority_queue<pair<int64_t, int64_t>, std::vector<pair<int64_t, int64_t>>, std::greater<pair<int64_t, int64_t>>> q; q.push({0, v}); while(!q.empty()){ pair<int64_t, int64_t> it = q.top(); q.pop(); if(vec[it.second] < it.first){ continue; } vec[it.second] = it.first; for(auto itt : graf[it.second]){ if(vec[itt.first] > it.first + itt.second){ vec[itt.first] = it.first + itt.second; q.push({vec[itt.first], itt.first}); } } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int64_t n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; graf.resize(n + 1); odl_s.resize(n + 1); odl_t.resize(n + 1); for(int64_t i = 0; i < m; i++){ int64_t a, b; int64_t c; cin >> a >> b >> c; kraw.push_back({{a, b}, c}); graf[a].push_back({b, c}); graf[b].push_back({a, c}); } for(int64_t i = 1; i <= n; i++){ odl_s[i] = 999999999999999999; odl_t[i] = 999999999999999999; } dijkstra(s, odl_s); dijkstra(t, odl_t); graf.clear(); graf.resize(400001); for(auto it : kraw){ int64_t a = it.first.first; int64_t b = it.first.second; int64_t c = it.second; // Normalny przed przejsciem graf[a].push_back({b, c}); graf[b].push_back({a, c}); // Normalny po przejsciem graf[a + 300000].push_back({b + 300000, c}); graf[b + 300000].push_back({a + 300000, c}); if(odl_s[a] + odl_t[b] + c == odl_s[t] || odl_s[b] + odl_t[a] + c == odl_s[t]){ if(odl_s[a] < odl_s[b]){ //Przejscie w jedna graf[a + 100000].push_back({b + 100000, 0}); //Przejscie w druga graf[b + 200000].push_back({a + 200000, 0}); }else{ //Przejscie w jedna graf[b + 100000].push_back({a + 100000, 0}); //Przejscie w druga graf[a + 200000].push_back({b + 200000, 0}); } } } for(int64_t i = 1; i <= n; i++){ //Przejscia powiedzy warstwami graf[i].push_back({i + 100000, 0}); graf[i].push_back({i + 200000, 0}); graf[i + 200000].push_back({i + 300000, 0}); graf[i + 100000].push_back({i + 300000, 0}); } odl_s.clear(); odl_s.resize(400001); for(int64_t i = 0; i < 4; i++){ for(int64_t j = 1; j <= n; j++){ odl_s[i * 100000 + j] = 999999999999999999; } } dijkstra(u, odl_s); cout << min(min(odl_s[v], odl_s[v + 100000]), min(odl_s[v + 200000], odl_s[v + 300000])); }