#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];
// trace_s holds the DAG of predecessors on *all* shortest s→x paths
vector<int> trace_s[100005];
// temporary trace array used inside Dijkstra (only when recording)
vector<int> trace_tmp[100005];
// store all s→t shortest paths in reverse (t→...→s)
vector<vector<int>> all_paths;
vector<int> current_path;
// Standard Dijkstra: if `record`==true, we fill trace_tmp[]
// otherwise we just compute distances
void dijkstra(int start, int *L, bool record) {
for (int i = 1; i <= n; i++) {
L[i] = INF;
if (record) trace_tmp[i].clear();
}
L[start] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.push({0, start});
while (!pq.empty()) {
auto [dist, node] = pq.top(); pq.pop();
if (dist > L[node]) continue;
for (auto [nei, w] : adj[node]) {
if (dist + w < L[nei]) {
L[nei] = dist + w;
if (record) {
trace_tmp[nei].clear();
trace_tmp[nei].push_back(node);
}
pq.push({L[nei], nei});
}
else if (record && dist + w == L[nei]) {
// another predecessor on a shortest path
trace_tmp[nei].push_back(node);
}
}
}
// if this was the run from s, snapshot trace_tmp → trace_s
if (record) {
for (int i = 1; i <= n; i++) {
trace_s[i] = trace_tmp[i];
}
}
}
// backtrack *all* reverse‐paths from `x` back to `s` using trace_s[]
void backtrack(int x) {
current_path.push_back(x);
if (x == s) {
all_paths.push_back(current_path);
} else {
for (int p : trace_s[x]) {
backtrack(p);
}
}
current_path.pop_back();
}
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) Run Dijkstra from s *with* recording
dijkstra(s, Ls, true);
// 2) Enumerate all shortest s→t paths (in reverse order t→...→s)
backtrack(t);
// 3) Run Dijkstra from u and v *without* recording
dijkstra(u, Lu, false);
dijkstra(v, Lv, false);
// 4) For each shortest s→t path, find the best meeting‐point split
int answer = INF;
for (auto &path : all_paths) {
// path is [t, ..., s], so we scan from back to front to go s→t
int bestLv = INF;
for (int i = (int)path.size() - 1; i >= 0; --i) {
bestLv = min(bestLv, Lv[path[i]]);
answer = min(answer, Lu[path[i]] + bestLv);
}
}
cout << answer << "\n";
return 0;
}
