#include <bits/stdc++.h>
#include <random>
using namespace std;
using ll = long long;
using ld = long double;
ll INF = 1e18;
vector<vector<pair<ll, ll>>> g;
ll n, m;
vector<ll> dex(ll start) {
vector<ll> dist(n, INF);
set<pair<ll, ll>> st;
dist[start] = 0;
st.insert({0, start});
while (!st.empty()) {
ll v = st.begin()->second;
ll mn = st.begin()->first;
st.erase(st.begin());
for (auto to: g[v]) {
if (dist[to.first] > to.second + mn) {
st.erase({dist[to.first], to.first});
dist[to.first] = mn + to.second;
st.insert({dist[to.first], to.first});
}
}
}
return dist;
}
vector<ll> all_good(ll start, ll p, vector<ll> &dist) {
vector<ll> good(n, 0);
deque<ll> q;
q.push_back(p);
good[p] = 1;
good[start] = 1;
while (!q.empty()) {
for (auto to: g[q.front()]) {
if (good[to.first] == 0) {
if (dist[to.first] + to.second == dist[q.front()]) {
good[to.first] = 1;
q.push_back(to.first);
}
}
}
q.pop_front();
}
return good;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
g.resize(n);
ll a, b;
cin >> a >> b;
ll v, u;
cin >> v >> u;
a--;
b--;
v--;
u--;
for (ll i = 0; i < m; i++) {
ll v1, v2, v3;
cin >> v1 >> v2 >> v3;
v1--;
v2--;
g[v1].emplace_back(v2, v3);
g[v2].emplace_back(v1, v3);
}
ll answer = INF;
{
vector<ll> dist = dex(a);
vector<ll> good = all_good(a, b, dist);
vector<ll> rast = dex(v);
answer = min(answer, rast[u]);
ll mn = INF;
ll ind = INF;
for (ll i = 0; i < good.size(); i++) {
if (good[i] == 1) {
if (mn > rast[i]) {
mn = rast[i];
ind = i;
}
}
}
vector<ll> cr = dex(ind);
vector<ll> proof1 = all_good(ind, b, cr);
vector<ll> proof2 = all_good(ind, a, cr);
vector<ll> last = dex(u);
for (ll i = 0; i < proof2.size(); i++) {
if (proof2[i] == 1 || proof1[i] == 1) {
answer = min(answer, mn + last[i]);
}
}
}
swap(u, v);
{
vector<ll> dist = dex(a);
vector<ll> good = all_good(a, b, dist);
vector<ll> rast = dex(v);
answer = min(answer, rast[u]);
ll mn = INF;
ll ind = INF;
for (ll i = 0; i < good.size(); i++) {
if (good[i] == 1) {
if (mn > rast[i]) {
mn = rast[i];
ind = i;
}
}
}
vector<ll> cr = dex(ind);
vector<ll> proof1 = all_good(ind, b, cr);
vector<ll> proof2 = all_good(ind, a, cr);
vector<ll> last = dex(u);
for (ll i = 0; i < proof2.size(); i++) {
if (proof2[i] == 1 || proof1[i] == 1) {
answer = min(answer, mn + last[i]);
}
}
}
cout << answer;
}
