#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const long long INF = 1e18;
struct Edge {
int to;
long long cost;
};
vector<long long> dijkstra(int start, const vector<vector<Edge>>& graph) {
int n = graph.size();
vector<long long> dist(n, INF);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
long long d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue;
for (const Edge& e : graph[u]) {
if (dist[u] + e.cost < dist[e.to]) {
dist[e.to] = dist[u] + e.cost;
pq.push({dist[e.to], e.to});
}
}
}
return dist;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
int S, T, U, V;
cin >> S >> T >> U >> V;
S--; T--; U--; V--; // Convert to 0-indexed
vector<vector<Edge>> graph(N);
for (int i = 0; i < M; i++) {
int a, b;
long long c;
cin >> a >> b >> c;
a--; b--; // Convert to 0-indexed
graph[a].push_back({b, c});
graph[b].push_back({a, c});
}
// Calculate shortest distances from all key points
vector<long long> distS = dijkstra(S, graph);
vector<long long> distT = dijkstra(T, graph);
vector<long long> distU = dijkstra(U, graph);
vector<long long> distV = dijkstra(V, graph);
long long shortestST = distS[T];
// Initialize result with direct path from U to V (no commuter pass used)
long long result = distU[V];
// The key insight: The commuter pass covers some shortest path from S to T.
// We can use this path for free in our journey from U to V.
// We need to consider all possible ways to utilize this free path:
// Strategy 1: Go U -> S -> T -> V (use entire S->T path)
result = min(result, distU[S] + distT[V]);
// Strategy 2: Go U -> T -> S -> V (use entire T->S path)
result = min(result, distU[T] + distS[V]);
// Strategy 3: Use intermediate points on the shortest S->T path
// For any point X that lies on some shortest path from S to T:
// - Distance from S to X plus distance from X to T equals shortestST
// - We can go U -> X -> V, using either S->X or X->T portion for free
for (int x = 0; x < N; x++) {
// Check if x lies on some shortest path from S to T
if (distS[x] + distT[x] == shortestST) {
// Case 3a: U -> X -> V, utilizing the fact that we can reach X from S for free
// or reach T from X for free (whichever is better)
result = min(result, distU[x] + distV[x]);
// Case 3b: U -> S -> X -> V (S->X is free)
result = min(result, distU[S] + distV[x]);
// Case 3c: U -> X -> T -> V (X->T is free)
result = min(result, distU[x] + distV[T]);
}
}
cout << result << endl;
return 0;
}
