#define NDEBUG
#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)
#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line: " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 2e18;
ll N,M,S,T,U,V;
//{to,wi}
vector<vector<pll>> road;
//{to, road num}
vector<vector<pll>> dag_out;
//{from, road num}
vector<vector<pll>> dag_in;
vector<ll> Vdist,Udist;
struct stat {
ll cost;
ll to;
ll from;
ll roadno;
bool operator <(const stat& oth) const {
return cost > oth.cost;
}
};
void djiktra(ll start, vector<ll>* costs) {
priority_queue<stat> dijkstraq;
dijkstraq.push({0,start,-1,-1});
while (!dijkstraq.empty()) {
auto [cost, curr, _1, _2] = dijkstraq.top();
dijkstraq.pop();
if ((*costs)[curr] != -1) {
assert((*costs)[curr]<=cost);
continue;
}
(*costs)[curr]=cost;
for (auto [next, wi] : road[curr])
{
dijkstraq.push({cost+wi, next, -1, -1});
}
}
}
vector<bool> goodnode;
void dfsgood(ll node) {
goodnode[node]=true;
for (auto [next, _] : dag_in[node])
{
dfsgood(next);
}
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cin >> N >> M >> S >> T >> U >> V;
S--; T--; U--; V--; // c
assert(U==S);
road.assign(N,{});
dag_out.assign(N,{});
dag_in.assign(N,{});
Vdist.assign(N,-1);
Udist.assign(N,-1);
goodnode.assign(N,false);
for (ll i = 0; i < M; ++i)
{
ll A,B,C;
cin >> A >> B >> C;
//A--; B--; //c
road[A].push_back({B,C});
road[B].push_back({A,C});
}
vector<ll> node_cost(N,-1);
//node_cost[S] = 0;
priority_queue<stat> dijkstraq;
dijkstraq.push({0,S,-1,-1});
while (!dijkstraq.empty()) {
auto [cost, curr, prev, roadno] = dijkstraq.top();
dijkstraq.pop();
dbg(curr <<":" <<cost);
if (node_cost[curr] != -1 && cost > node_cost[curr]) {
continue;
}
dbgv(curr <<":" <<cost);
assert(node_cost[curr]==cost || node_cost[curr]==-1);
node_cost[curr] = cost;
if (prev!=-1) {
dag_out[prev].push_back({curr, roadno});
dag_in[curr].push_back({prev, roadno});
}
for (ll i = 0; i < ll(road[curr].size()); ++i)
{
auto [next, wi] = road[curr][i];
dijkstraq.push({cost+wi, next, curr,i});
}
}
dbg("hmm1");
dfsgood(T);
dbg("hmm2");
djiktra(V,&Vdist);
djiktra(U,&Udist);
ll outp=INFTY;
ll o2=INFTY;
dbg("hmm3");
for (ll i = 0; i < N; ++i)
{
dbgv(i << " " << Vdist[i] << " " << goodnode[i]);
if (goodnode[i]) {
outp = min(outp,Vdist[i]);
o2 = min(outp,Udist[i]);
}
}
cout << outp+o2;
}
