#include <iostream>
#include <vector>
#include <queue>
using namespace std;
static const int INF = 1e9;
int n, m, s, t, u, v;
int Ls[100005], Lu[100005], Lv[100005];
vector<pair<int,int>> adj[100005];
vector<int> trace[100005];
int answer = INF;
// Standard Dijkstra: when calc==true we also build the predecessor‐lists in trace[]
void dijkstra(int start, int *L, bool calc) {
for(int i = 1; i <= n; i++) {
L[i] = INF;
if(calc) trace[i].clear();
}
L[start] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.push({0, start});
while(!pq.empty()) {
auto [d, x] = pq.top(); pq.pop();
if(d > L[x]) continue;
for(auto [y, w] : adj[x]) {
if(d + w < L[y]) {
L[y] = d + w;
if(calc) {
trace[y].clear();
trace[y].push_back(x);
}
pq.push({L[y], y});
}
else if(calc && d + w == L[y]) {
// another shortest‐path predecessor
trace[y].push_back(x);
}
}
}
}
// DFS from t back to s, carrying along the best (min) Lu[] and Lv[] seen so far
void back(int x, int best_u, int best_v) {
best_u = min(best_u, Lu[x]);
best_v = min(best_v, Lv[x]);
if(x == s) {
// we've reached s, record candidate answer
answer = min(answer, best_u + best_v);
return;
}
for(int p : trace[x]) {
back(p, best_u, best_v);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> s >> t >> u >> v;
for(int i = 0; i < m; i++){
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
// 1) Distances from u and v (no tracing needed)
dijkstra(u, Lu, false);
dijkstra(v, Lv, false);
// 2) Distances *and* trace‐lists from s
dijkstra(s, Ls, true);
// 3) Explore every shortest s→t path by DFS from t back to s
back(t, INF, INF);
cout << answer << "\n";
return 0;
}
