#include <iostream>
#include <queue>
#include <vector>
#define int long long
using namespace std;
const int MAX_SOMMET = 1e5+42;
struct Arete{
int dest, cost;
};
struct Pq{
int sommet, dist, type;
bool operator<(const Pq &autre) const {
return dist > autre.dist;
}
};
int nbSommet, nbArete;
int debOpti, finOpti, debReq, finReq;
vector<Arete> adj[MAX_SOMMET];
void input() {
cin >> nbSommet >> nbArete;
cin >> debOpti >> finOpti >> debReq >> finReq;
debOpti--; finOpti--; debReq--; finReq--;
for(int arete = 0; arete < nbArete; arete++) {
int u,v,c;
cin >> u >> v >> c;
adj[--u].push_back({--v, c});
adj[v].push_back({u, c});
}
}
int prof[MAX_SOMMET] = {0};
bool vu[MAX_SOMMET][4] = {0};
int ordre[MAX_SOMMET] = {0};
int dist[MAX_SOMMET];
bool vuOrdre[MAX_SOMMET] = {0};
void calcOrdre(int sommet, int curOrdre) {
if(vuOrdre[sommet]) {
return;
}
vuOrdre[sommet] = 1;
ordre[sommet] = curOrdre;
for(auto voisin : adj[sommet]) {
if(dist[sommet] == dist[voisin.dest] + voisin.cost) {
calcOrdre(voisin.dest, curOrdre+1);
}
}
}
void pcc(int deb, int fin) {
for(int sommet = 0; sommet < MAX_SOMMET; sommet++) {
for(int type = 0; type < 4; type++) {
vu[sommet][type] = 0;
}
}
priority_queue<Pq> q;
if(ordre[deb] == 0) {
q.push({deb, 0, 0});
}
else {
q.push({deb, 0, 1});
q.push({deb, 0, 2});
}
while(!q.empty()) {
Pq cur = q.top();
q.pop();
if(vu[cur.sommet][cur.type]) {
continue;
}
vu[cur.sommet][cur.type] = 1;
if(deb == debOpti) {
dist[cur.sommet] = cur.dist;
}
if(cur.sommet == fin && deb == debReq && fin == finReq) {
cout << cur.dist << endl;
return;
}
for(auto voisin : adj[cur.sommet]) {
if(ordre[voisin.dest] == 0) {
int typeNouv = 0;
if(cur.type > 0) {
typeNouv = 3;
}
q.push({voisin.dest, cur.dist + voisin.cost, typeNouv});
}
else {
if(cur.type == 0) {
q.push({voisin.dest, cur.dist + voisin.cost, 1});
q.push({voisin.dest, cur.dist + voisin.cost, 2});
}
if(cur.type == 1 && ordre[cur.sommet] + 1 == ordre[voisin.dest]) {
q.push({voisin.dest, cur.dist, 1});
}
if(cur.type == 2 && ordre[cur.sommet] == ordre[voisin.dest] + 1) {
q.push({voisin.dest, cur.dist, 2});
}
q.push({voisin.dest, cur.dist + voisin.cost, 3});
}
}
}
}
signed main() {
input();
pcc(debOpti, finOpti);
calcOrdre(finOpti, 1);
pcc(debReq, finReq);
}
