#include <bits/stdc++.h>
#define TASK "commuter_pass"
#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];
priority_queue<ill, vector<ill>, cmp> qx;
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});
}
}
}
}
ll rdist[MAX][2][2];
priority_queue<state> qrx;
ll result = LLONG_MAX;
bool IN_PATH(int v1, int v2, int w)
{
return fdist[0][v1] + fdist[1][v2] + w == fdist[0][free_end];
}
void DIJKSTRA_RUN(int z_start, int z_end)
{
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[z_start][0][0] = 0;
qrx.push(state(z_start, 0, 0, 0));
while (qrx.size())
{
int cv = qrx.top().v;
ll cw = qrx.top().w;
bool cc1 = qrx.top().cont, cc2 = qrx.top().cur_cont;
qrx.pop();
if (cw > rdist[cv][cc1][cc2])
continue;
if (cv == z_end)
break;
for (auto itr : e[cv])
{
int nv = itr.f, nxw = itr.s;
if (rdist[nv][cc1][0] > cw + nxw)
{
rdist[nv][cc1][0] = cw + nxw;
qrx.push(state(nv, cw + nxw, cc1, 0));
}
if (IN_PATH(cv, nv, nxw))
{
if (cc1 && !cc2)
continue;
if (rdist[nv][1][1] > cw)
{
rdist[nv][1][1] = cw;
qrx.push(state(nv, cw, 1, 1));
}
}
}
}
result = min({result, rdist[z_end][1][1], rdist[z_end][1][0], rdist[z_end][0][0]});
}
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;
}
