#include <bits/stdc++.h>
using namespace std;
#ifdef local
#include "debug.hpp"
#define pr(...) debug(#__VA_ARGS__, __VA_ARGS__)
#define prs(...) debug_nameless(__VA_ARGS__)
#else
#define pr(...) 69
#define prs(...) 69
#endif
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using i128 = __int128;
using u128 = unsigned __int128;
const i64 inf = 1e9+1;
const i64 binf = 2e13;
/*
seja o caminho S-T: a_1 a_2 ... a_n
seja o caminho U-V: b_1 b_2 ... b_m
lema:
os vértices em comum aos dois são um subcaminho (tanto de S-T quanto de U-V)
prova:
se tem apenas um vertice em comum, isso é óbvio.
se tem dois vértices em comum, o caminho entre eles pode ser comum.
*colapsar esse caminho em ambos, pra virar um vértice*
repetir esse argumento indutivamente.
solução naive: testar todos (x, y)
solução rápida: considerar o DAG do dijktras saindo de S.
pra cada vértice x, tenho que achar algum y tal que:
1. y chegue em T.
2. distancia x->V é minima.
definimos f(x) como:
inf, se y nao chega em T
dist(x -> V), caso contrario
calcular dp[x] := min(f(v)) para todo v visto por x
no final, achar min(dp[x] + dist(U->x))
*/
struct Graph{
int n;
vector <vector<pair<int,int>>> adj;
Graph(int n){
this->n = n;
adj.resize(n);
}
void add_edge(int u, int v, int w){
adj[u].emplace_back(v, w);
}
vector<i64> dijkstras(int source, vector<array<int,3>>& edges){
vector <i64> dist(n, binf);
dist[source] = 0;
set <pair<i64, int>> s;
for(int i = 0; i < n; i++){
s.insert({dist[i], i});
}
while(s.size() > 0){
auto [d, node] = *s.begin();
s.erase(s.begin());
for(auto [nei, w] : adj[node]){
if(dist[node]+w < dist[nei]){
s.erase({dist[nei], nei});
dist[nei] = dist[node]+w;
s.insert({dist[nei], nei});
}
if(dist[node]+w == dist[nei]){
edges.push_back({node, nei, w});
}
}
}
return dist;
}
i64 calc(int s, int t, int u, int v, vector<i64>& dist_u, vector<i64>& dist_v){
vector <bool> valid(n, false), vis(n, false);
valid[t] = true;
function <void(int)> dfs = [&](int node){
vis[node] = true;
for(auto [nei, w] : adj[node]){
if(!vis[nei]){
dfs(nei);
}
valid[node] = valid[node] || valid[nei];
}
};
dfs(s);
vector <array<int,3>> tmp;
vector <i64> dp(n, binf);
fill(vis.begin(), vis.end(), false);
dfs = [&](int node){
vis[node] = true;
if(valid[node]){
dp[node] = dist_v[node];
}
for(auto [nei, w] : adj[node]){
if(!vis[nei]){
dfs(nei);
}
dp[node] = min(dp[node], dp[nei]);
}
};
dfs(s);
pr(dp, valid, dist_v);
i64 ans = binf;
for(int i = 0; i < n; i++){
ans = min(ans, dp[i] + dist_u[i]);
}
fill(dp.begin(), dp.end(), binf);
fill(vis.begin(), vis.end(), false);
dfs = [&](int node){
vis[node] = true;
if(valid[node]){
dp[node] = dist_u[node];
}
for(auto [nei, w] : adj[node]){
if(!vis[nei]){
dfs(nei);
}
dp[node] = min(dp[node], dp[nei]);
}
};
dfs(s);
for(int i = 0; i < n; i++){
ans = min(ans, dp[i] + dist_v[i]);
}
return ans;
}
};
void solve(int tc){
int n, m;
cin >> n >> m;
int s, t, u, v;
cin >> s >> t >> u >> v;
s -= 1, t -= 1, u -= 1, v -= 1;
Graph ori(n);
for(int i = 0; i < m; i++){
int u, v, w;
cin >> u >> v >> w;
u -= 1, v -= 1;
ori.add_edge(u, v, w);
ori.add_edge(v, u, w);
}
pr("uepa");
vector <array<int,3>> edges;
ori.dijkstras(s, edges);
pr(edges);
Graph dag(n);
for(auto [u, v, w] : edges){
dag.add_edge(u, v, w);
}
vector <array<int,3>> tmp;
auto dist_v = ori.dijkstras(v, tmp);
auto dist_u = ori.dijkstras(u, tmp);
pr(dist_v[u]);
cout << min(dist_v[u], dag.calc(s, t, u, v, dist_u, dist_v)) << "\n";
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tc = 1;
// cin >> tc;
for(int t = 0; t < tc; t++){
pr(t); prs(string(50, '-'));
solve(t);
prs(string(50, '-') + "\n");
}
return 0;
}
