///
/// "People's Dreams.. Never End!!"
///
/// ~Marshall D. Teach
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define mk make_pair
#define endl cout << '\n'
#define haha cerr << "haha\n"
#define all(x) x.begin(), x.end()
#define kill(x) exit((cout << (x) << '\n', 0))
#define yn(flag) ((flag) ? "YES\n": "NO\n")
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2")
ll const inf = 1'000'000'000'000'000 + 10;
ll const mod = 1'000'000'000 + 7;
ll const maxn = 300'000 + 10;
ll const base = 337;
ll const sq = 320;
ll n;
ll dis[maxn];
set<pll> s;
vector<pll> adj[maxn];
vector<ll> vec[maxn];
ll dij(ll x, ll y) {
fill(dis, dis + 3 * n, inf);
dis[x] = 0;
s.clear();
s.insert(mk(0, x));
while (s.size()) {
auto [d, v] = *s.begin();
s.erase(mk(d, v));
for (auto [u, w] : adj[v]) {
if (dis[u] > d + w) {
s.erase(mk(dis[u], u));
dis[u] = d + w;
s.insert({dis[u], u});
vec[u].clear();
vec[u].pb(v);
} else if (dis[u] == d + w) {
vec[u].pb(v);
}
}
}
return dis[y];
}
bool mark[maxn];
void build1() {
for (ll i = n; i < 2 * n; ++i) {
if (mark[i - n])
for (auto u : vec[i - n]) {
adj[u + n].pb({i, 0});
}
}
for (ll i = 2 * n; i < 3 * n; ++i) {
for (auto u : adj[i - 2 * n])
adj[i].pb({u.F + 2 * n, u.S});
}
for (ll i = 0; i < n; ++i) {
adj[i].pb({i + n, 0});
adj[i + n].pb({i + 2 * n, 0});
}
}
void dfs(ll v) {
mark[v] = true;
for (auto u : vec[v]) {
if (!mark[u])
dfs(u);
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
ll m;
cin >> n >> m;
ll a, b, u, v;
cin >> a >> b >> u >> v;
--a, --b, --u, --v;
for (ll i = 0; i < m; ++i) {
ll a, b, c;
cin >> a >> b >> c;
--a, --b;
adj[a].pb(mk(b, c));
adj[b].pb(mk(a, c));
}
dij(a, b);
dfs(b);
build1();
cout << min(dij(u, v + n + n), dij(v, u + n + n)) << '\n';
}
// check before submiting :
// maxn (please check this shit)
