#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <set>
using namespace std;
#define ll long long
#define INF 1e17
#define X first
#define Y second
vector<pair<int, int>> stage[100005];
vector<ll> sdist, udist, vdist;
bool status[100005];
queue<int> q;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
multiset<ll> ums, vms;
set<int> path, blocked;
void dijkstra(vector<ll>& dist, int s)
{
fill(dist.begin(), dist.end(), INF);
dist[s] = 0;
pq.push({0, s});
while(!pq.empty())
{
ll d; int cur;
tie(d, cur) = pq.top(); pq.pop();
if(dist[cur] != d)
continue;
for(auto& nxt : stage[cur])
if(dist[nxt.X] > d + nxt.Y)
{
dist[nxt.X] = d + nxt.Y;
pq.push({dist[nxt.X], nxt.X});
}
}
}
void dfs(int cur, ll& ans)
{
ums.insert(udist[cur]);
vms.insert(vdist[cur]);
ans = min(ans, *ums.begin()+*vms.begin());
int tmp = 0;
for(auto& nxt : stage[cur])
if(sdist[nxt.X] + nxt.Y == sdist[cur])
tmp++;
if(tmp > 1)
{
int pre = -1;
for(int i = 0; i < (int)stage[cur].size(); i++)
{
auto& nxt = stage[cur][i];
if(sdist[nxt.X] + nxt.Y == sdist[cur])
{
path.clear();
blocked.clear();
q.push(nxt.X);
path.insert(nxt.X);
while(!q.empty())
{
int elem = q.front(); q.pop();
ums.insert(udist[elem]);
vms.insert(vdist[elem]);
for(auto& nxt : stage[elem])
{
if(sdist[nxt.X] + nxt.Y == sdist[elem])
{
if(!status[nxt.X])
{
q.push(nxt.X);
path.insert(nxt.X);
}
else if(path.count(nxt.X))
continue;
else
blocked.insert(nxt.X);
}
}
}
if(pre != -1)
{
q.push(pre);
while(!q.empty())
{
int elem = q.front(); q.pop();
ums.erase(ums.find(udist[elem]));
vms.erase(vms.find(vdist[elem]));
for(auto& nxt : stage[elem])
if(sdist[nxt.X] + nxt.Y == sdist[elem] && !blocked.count(nxt.X))
q.push(nxt.X);
}
}
ans = min(ans, *ums.begin()+*vms.begin());
pre = nxt.X;
for(int x : path)
status[x] = 1;
}
}
return;
}
else
{
for(auto& nxt : stage[cur])
if(sdist[nxt.X] + nxt.Y == sdist[cur])
dfs(nxt.X, ans);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
while(m--)
{
int a, b, c;
cin >> a >> b >> c;
stage[a].push_back({b, c});
stage[b].push_back({a, c});
}
sdist.resize(n+1); udist.resize(n+1); vdist.resize(n+1);
dijkstra(sdist, s);
dijkstra(udist, u);
dijkstra(vdist, v);
ll ans = udist[v];
dfs(t, ans);
cout << ans << '\n';
}
