#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});
}
}
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, s});
vector<vector<pair<ll, ll>>> states(n);
auto add = [&](int node, pair<ll, ll> state) -> void {
if (states[node].empty()) {
for (int i = 0; i < 3; ++i) {
states[node].push_back(state);
}
return;
}
if ((state.first < states[node][0].first) || (state.first == states[node][0].first && state.second < states[node][0].second)) {
states[node][0] = state;
}
if ((state.second < states[node][1].second) || (state.second == states[node][1].second && state.first < states[node][1].first)) {
states[node][1] = state;
}
if (state.first + state.second < states[node][2].first + states[node][2].second) {
states[node][2] = state;
}
};
add(s, {toU[s], toV[s]});
vector<ll> best(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;
if (node == t) {
cout << min(toU[v], states[node][2].first + states[node][2].second) << '\n';
return 0;
}
for (int i = 0; i < 3; ++i) {
states[node][i].first = min(states[node][i].first, toU[node]);
states[node][i].second = min(states[node][i].second, toV[node]);
}
for (pair<int, int>& edge : adj[node]) {
if (d + edge.second < best[edge.first]) {
best[edge.first] = d + edge.second;
states[edge.first].clear();
pq.push({d + edge.second, edge.first});
}
for (int i = 0; i < 3; ++i) {
if (d + edge.second == best[edge.first]) {
add(edge.first, states[node][i]);
}
}
}
}
return 0;
}
