#include <bits/stdc++.h>
#define TASK "bus"
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ll> ill;
typedef pair<ll, int> lli;
typedef pair<ll, ll> pll;
const int MAX = 1e5 + 10;
const int MOD = 1e9 + 7;
class state
{
public:
int v;
ll w;
bool cont, cur_cont;
state() { v = w = cont = cur_cont = 0; }
state(const int &I_v, const ll &I_w, const bool &I_cont, const bool &I_ccont)
{
v = I_v;
w = I_w;
cont = I_cont;
cur_cont = I_ccont;
}
bool operator<(const state &SE) const { return w > SE.w; }
};
struct cmp
{
bool operator()(ill FI, ill SE) { return FI.s > SE.s; }
};
int n, m, free_start, free_end, p_start, p_end;
vector<ii> e[MAX];
ll fdist[2][MAX], rdist[MAX][2][2];
priority_queue<ill, vector<ill>, cmp> qx;
priority_queue<state> qrx;
ll result = LLONG_MAX;
void DIJKSTRA_BUILD(int start, int nt)
{
for (int i = 1; i <= n; ++i)
fdist[nt][i] = LLONG_MAX;
fdist[nt][start] = 0;
qx.push({start, 0});
while (qx.size())
{
int cv = qx.top().f;
ll cw = qx.top().s;
qx.pop();
if (fdist[nt][cv] < cw)
continue;
for (auto itr : e[cv])
{
int nv = itr.f, nxw = itr.s;
if (fdist[nt][nv] > cw + nxw)
{
fdist[nt][nv] = cw + nxw;
qx.push({nv, cw + nxw});
}
}
}
}
bool IN_PATH(int x)
{
return fdist[0][x] + fdist[1][x] == fdist[0][free_end];
}
void DIJKSTRA_RUN(int start, int finish)
{
while (qrx.size())
qrx.pop();
for (int i = 1; i <= n; ++i)
for (int j = 0; j < 2; ++j)
rdist[i][j][0] = rdist[i][j][1] = LLONG_MAX;
rdist[start][0][0] = 0;
qrx.push(state(start, 0, 0, 0));
if (IN_PATH(start))
{
rdist[start][0][1] = 0;
qrx.push(state(start, 0, 0, 1));
}
while (qrx.size())
{
int cv = qrx.top().v;
ll cw = qrx.top().w;
bool freed = qrx.top().cont, cfree = qrx.top().cur_cont;
qrx.pop();
if (cw > rdist[cv][freed][cfree])
continue;
if (cv == finish)
{
result = min(result, cw);
return;
}
for (auto itr : e[cv])
{
int nv = itr.f, nxw = itr.s;
ll ncw;
bool n_freed = freed, n_cfree;
if (cfree)
{
ncw = cw;
if (IN_PATH(nv))
n_cfree = n_freed = 1;
else
{
n_cfree = 0;
ncw += nxw;
}
}
else
{
ncw = cw + nxw;
if (!IN_PATH(nv))
n_cfree = 0;
else if (n_freed)
n_freed = n_cfree = 0;
else
n_cfree = 1;
}
if (rdist[nv][n_freed][n_cfree] > ncw)
{
rdist[nv][n_freed][n_cfree] = ncw;
qrx.push(state(nv, ncw, n_freed, n_cfree));
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen(TASK ".inp", "r"))
{
freopen(TASK ".inp", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
cin >> n >> m >> free_start >> free_end >> p_start >> p_end;
while (m--)
{
int u1, u2, uw;
cin >> u1 >> u2 >> uw;
e[u1].push_back({u2, uw});
e[u2].push_back({u1, uw});
}
DIJKSTRA_BUILD(free_start, 0);
DIJKSTRA_BUILD(free_end, 1);
DIJKSTRA_RUN(p_start, p_end);
DIJKSTRA_RUN(p_end, p_start);
cout << result;
}
