#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
int s, t; cin >> s >> t;
int u, v; cin >> u >> v;
--s; --t; --u; --v;
vector<vector<pair<int, int>>> adj(n);
while (m--) {
int a, b, c; cin >> a >> b >> c;
adj[--a].push_back({--b, c});
adj[b].push_back({a, c});
}
vector<ll> toU(n, INT64_MAX), toV(n, INT64_MAX);
{
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, u});
while (!pq.empty()) {
ll d = pq.top().first;
int node = pq.top().second;
pq.pop();
if (toU[node] != INT64_MAX) continue;
toU[node] = d;
for (pair<int, int>& edge : adj[node]) {
pq.push({d + edge.second, edge.first});
}
}
}
{
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, v});
while (!pq.empty()) {
ll d = pq.top().first;
int node = pq.top().second;
pq.pop();
if (toV[node] != INT64_MAX) continue;
toV[node] = d;
for (pair<int, int>& edge : adj[node]) {
pq.push({d + edge.second, edge.first});
}
}
}
ll ans = INT64_MAX;
{
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, s});
vector<ll> bestV(n, INT64_MAX), best(n, INT64_MAX), toget(n, INT64_MAX);
vector<bool> vis(n);
while (!pq.empty()) {
ll d = pq.top().first;
int node = pq.top().second;
pq.pop();
if (vis[node]) continue;
vis[node] = true;
bestV[node] = min(bestV[node], toV[node]);
best[node] = min(best[node], bestV[node] + toU[node]);
if (node == t) {
ans = min(ans, best[node]);
break;
}
for (pair<int, int>& edge : adj[node]) {
if (d + edge.second < toget[edge.first]) {
toget[edge.first] = d + edge.second;
bestV[edge.first] = bestV[node];
best[edge.first] = best[node];
pq.push({d + edge.second, edge.first});
} else if (d + edge.second == toget[edge.first]) {
bestV[edge.first] = min(bestV[edge.first], bestV[node]);
best[edge.first] = min(best[edge.first], best[node]);
}
}
}
}
{
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, t});
vector<ll> bestV(n, INT64_MAX), best(n, INT64_MAX), toget(n, INT64_MAX);
vector<bool> vis(n);
while (!pq.empty()) {
ll d = pq.top().first;
int node = pq.top().second;
pq.pop();
if (vis[node]) continue;
vis[node] = true;
bestV[node] = min(bestV[node], toV[node]);
best[node] = min(best[node], bestV[node] + toU[node]);
if (node == s) {
ans = min(ans, best[node]);
break;
}
for (pair<int, int>& edge : adj[node]) {
if (d + edge.second < toget[edge.first]) {
toget[edge.first] = d + edge.second;
bestV[edge.first] = bestV[node];
best[edge.first] = best[node];
pq.push({d + edge.second, edge.first});
} else if (d + edge.second == toget[edge.first]) {
bestV[edge.first] = min(bestV[edge.first], bestV[node]);
best[edge.first] = min(best[edge.first], best[node]);
}
}
}
}
cout << min(ans, toV[u]) << '\n';
return 0;
}
