#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;
struct Edge {
int u, v;
int w;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
int S, T, U, V;
if (!(cin >> n >> m >> S >> T >> U >> V)) return 0;
vector<Edge> edges(m+1);
vector<vector<pair<int,int>>> adj(n+1);
for (int i = 1; i <= m; ++i) {
int a, b, c; cin >> a >> b >> c;
edges[i] = {a,b,c};
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
auto dijkstra_from = [&](int src) {
vector<ll> dist(n+1, INF);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d != dist[u]) continue;
for (auto [v, eid] : adj[u]) {
int w = edges[eid].w;
if (dist[v] > d + w) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
return dist;
};
vector<ll> distS = dijkstra_from(S);
vector<ll> distT = dijkstra_from(T);
vector<ll> distU = dijkstra_from(U);
vector<ll> distV = dijkstra_from(V);
// Mark edges that lie on some shortest path from S to T and build directed DAG (forward along distS)
vector<vector<int>> dag(n+1);
for (int i = 1; i <= m; ++i) {
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
// if u->v is forward on some shortest S->T path
if (distS[u] + w + distT[v] == distS[T] && distS[u] + w == distS[v]) {
dag[u].push_back(v);
}
if (distS[v] + w + distT[u] == distS[T] && distS[v] + w == distS[u]) {
dag[v].push_back(u);
}
}
// sort vertices by distS (increasing). Edges in dag go from smaller distS to larger distS
vector<int> ord(n);
for (int i = 0; i < n; ++i) ord[i] = i+1;
sort(ord.begin(), ord.end(), [&](int a, int b){ return distS[a] < distS[b]; });
auto solve_with_shop = [&](const vector<ll>& distShop) {
// DP: best[u] = minimal value of min(distShop[x]) along any path from S to u in DAG
vector<ll> best(n+1, INF);
best[S] = distShop[S];
ll res = INF;
for (int u : ord) {
if (best[u] == INF) continue; // unreachable in DAG from S
// candidate answer: choose route such that up to u we use zero cost, then pay distV[u]
res = min(res, best[u] + distV[u]);
for (int v : dag[u]) {
ll cand = min(best[u], distShop[v]);
if (cand < best[v]) best[v] = cand;
}
}
return res;
};
// Two possibilities: choose route and pay remaining either using shop U->V or swap shops?
// The original logic runs solve starting from shop1 and then swap shop1/shop2; we mimic that:
vector<ll> distShop1 = distU;
vector<ll> distShop2 = distV;
// first candidate: no zero-route used (just pay direct U->V)
ll answer = min(distShop1[V], distShop2[U]); // direct without any road chosen (both directions considered)
// try using DAG + shop1 as "free" source along route
ll cand1 = solve_with_shop(distShop1);
// now swap roles: we want shop2 as free-source and distU used as distV vector in lambda, so we need to rebuild lambda using other distV
// simplest: swap global distV (used in lambda). We'll implement solve_with_shop2 to use distU as second distance:
// For clarity, duplicate function to use appropriate distal second term.
auto solve_with_shop_and_other = [&](const vector<ll>& distShop, const vector<ll>& otherDist) {
vector<ll> best(n+1, INF);
best[S] = distShop[S];
ll res2 = INF;
for (int u : ord) {
if (best[u] == INF) continue;
res2 = min(res2, best[u] + otherDist[u]);
for (int v : dag[u]) {
ll cand = min(best[u], distShop[v]);
if (cand < best[v]) best[v] = cand;
}
}
return res2;
};
ll candA = solve_with_shop_and_other(distShop1, distV); // original: best + dis_shop2[u] where shop2==V
ll candB = solve_with_shop_and_other(distShop2, distU); // swapped roles
answer = min(answer, min({candA, candB}));
if (answer >= INF/4) answer = -1; // if unreachable, depends on problem statement (but keep existing)
cout << answer << "\n";
return 0;
}
