#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1000000;
#define int long long
const int INFINI = 1e15;
struct T {
int noeud, temps;
bool operator<(const T &other) const {
return temps > other.temps;
}
};
int nbVilles, nbChemins, maison, ecole, point1, point2;
vector<T> chemins[NMAX];
int distancePoint[2][NMAX];
int dejaVu[NMAX];
vector<int> anc[NMAX];
struct C {
int noeud, temps, dernier;
bool operator<(const C &other) const {
return temps > other.temps;
}
};
pair<int, int> dejaVuMinCout[NMAX];
bool vu[NMAX];
pair<int, int> trouverMinCout(int noeud)
{
if(noeud == -1) return pair<int, int>(INFINI, INFINI);
if(vu[noeud]) return dejaVuMinCout[noeud];
int meillPoint[2] = {distancePoint[0][noeud], distancePoint[1][noeud]};
//cout << noeud << " : " << meillPoint[0] << " " << meillPoint[1] << endl;
int meill = INFINI, meill1 = INFINI, meill2 = INFINI;
for(int pro : anc[noeud])
{
auto rev = trouverMinCout(pro);
int score = min(rev.first+rev.second, min(rev.first + meillPoint[1], rev.second+meillPoint[0]));
if(meill > score)
{
meill = score;
meill1 = rev.first;
meill2 = rev.second;
}
}
meillPoint[0] = min(meillPoint[0], meill1);
meillPoint[1] = min(meillPoint[1], meill2);
vu[noeud] = true;
//cout << noeud << " : " << meillPoint[0] << " " << meillPoint[1] << endl;
return dejaVuMinCout[noeud] = pair<int, int>(meillPoint[0], meillPoint[1]);
}
int miniTemps[NMAX];
signed main() {
// your code goes here
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> nbVilles >> nbChemins >> maison >> ecole >> point1 >> point2;
--maison;
--ecole;
--point1;
--point2;
for(int iChemin = 0; iChemin < nbChemins; iChemin++)
{
int a, b, t;
cin >> a >> b >> t;
--a;
--b;
chemins[a].push_back({b, t});
chemins[b].push_back({a, t});
}
for(int i = 0; i < nbVilles; i++)
{
miniTemps[i] = INFINI;
}
for(int i = 0; i < 2; i++)
{
priority_queue<T> plusCourtChemin;
plusCourtChemin.push({point1, 0});
while(plusCourtChemin.size())
{
auto sit = plusCourtChemin.top();
plusCourtChemin.pop();
if(dejaVu[sit.noeud] == i+1)
continue;
dejaVu[sit.noeud] = i+1;
distancePoint[i][sit.noeud] = sit.temps;
for(auto pro : chemins[sit.noeud])
{
plusCourtChemin.push({pro.noeud, pro.temps+sit.temps});
}
}
swap(point1, point2);
}
/*
for(int i = 0; i < 2; i++)
{
for(int n = 0; n < nbVilles;n++)
{
cout << distancePoint[i][n] << " ";
}
cout << endl;
}
/** */
priority_queue<C> plusCourtChemin2;
plusCourtChemin2.push({maison, 0, -1});
while(plusCourtChemin2.size())
{
auto sit = plusCourtChemin2.top();
plusCourtChemin2.pop();
miniTemps[sit.noeud] = min(miniTemps[sit.noeud], sit.temps);
//cout << sit.noeud << " " << sit.dernier << " " << sit.temps << endl;
if(sit.temps == miniTemps[sit.noeud])
{
//cout << "Bon" << endl;
anc[sit.noeud].push_back(sit.dernier);
}
else
continue;
if(sit.noeud == ecole)
{
continue;
}
int a = 0;
for(auto pro : chemins[sit.noeud])
{
a ++;
plusCourtChemin2.push({pro.noeud, pro.temps+sit.temps, sit.noeud});
}
//cout << a << endl;
}
/**
for(int i = 0; i < nbVilles; i++)
{
for(auto a : anc[i]) cout << a <<" ";
cout <<endl;
}
cout << endl;
//return 0;
/** */
pair<int, int> res = trouverMinCout(ecole);
cout << min(res.first + res.second, distancePoint[0][point2]);
}
