#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 1e16; // Προσοχή στο INF για να μην έχουμε overflow
struct Edge {
int to;
ll weight;
};
struct Node {
int id;
ll dist;
bool operator>(const Node& other) const {
return dist > other.dist;
}
};
int N, M;
vector<Edge> adj[100005];
void dijkstra(int start, vector<ll>& dists) {
dists.assign(N + 1, INF);
priority_queue<Node, vector<Node>, greater<Node>> pq;
dists[start] = 0;
pq.push({start, 0});
while (!pq.empty()) {
Node curr = pq.top(); pq.pop();
if (curr.dist > dists[curr.id]) continue;
for (auto& e : adj[curr.id]) {
if (dists[curr.id] + e.weight < dists[e.to]) {
dists[e.to] = dists[curr.id] + e.weight;
pq.push({e.to, dists[e.to]});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int s, t, a, b;
if (!(cin >> N >> M)) return 0;
cin >> s >> t >> a >> b;
for (int i = 0; i < M; i++) {
int u, v; ll c;
cin >> u >> v >> c;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
// 4 Dijkstra για να ξέρουμε αποστάσεις από όλα τα κρίσιμα σημεία
vector<ll> dS, dT, dA, dB;
dijkstra(s, dS);
dijkstra(t, dT);
dijkstra(a, dA);
dijkstra(b, dB);
ll minST = dS[t];
ll result = dA[b]; // Αρχική τιμή: το απλό συντομότερο a-b
// Δημιουργούμε ένα DAG με τις ακμές που ανήκουν σε συντομότερα s-t μονοπάτια
vector<int> dag_adj[100005];
vector<int> in_degree(N + 1, 0);
for (int u = 1; u <= N; u++) {
for (auto& e : adj[u]) {
if (dS[u] + e.weight + dT[e.to] == minST) {
dag_adj[u].push_back(e.to);
in_degree[e.to]++;
}
}
}
// DP πάνω στο DAG για να βρούμε το μέγιστο "κέρδος" (δωρεάν διαδρομή)
// d_overlap[u]: η ελάχιστη απόσταση από το 'a' στο 'u' αν χρησιμοποιήσουμε
// ένα τμήμα του s-t μονοπατιού που καταλήγει στο u.
vector<ll> dp_a(N + 1, INF), dp_b(N + 1, INF);
// Τοπική ταξινόμηση (Topological Sort) για το DAG
queue<int> q;
for (int i = 1; i <= N; i++) if (in_degree[i] == 0) q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
// Η απόσταση στο u μπορεί να είναι η απευθείας από το 'a'
// ή να συνεχίζει από έναν προκάτοχο στο DAG με κόστος 0
dp_a[u] = min(dp_a[u], dA[u]);
dp_b[u] = min(dp_b[u], dB[u]);
result = min(result, dp_a[u] + dB[u]);
result = min(result, dp_b[u] + dA[u]);
for (int v : dag_adj[u]) {
dp_a[v] = min(dp_a[v], dp_a[u]);
dp_b[v] = min(dp_b[v], dp_b[u]);
if (--in_degree[v] == 0) q.push(v);
}
}
cout << result << endl;
return 0;
}
