#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Vertice {
int start, end, cost;
};
struct compare {
bool operator() (Vertice a, Vertice b) {
return a.cost > b.cost;
}
};
vector<Vertice> graph[100100];
vector<vector<Vertice>> minGraph(100100);
bool done[100100];
int costMin[100100], costMinA[100100], costMinB[100100], costMinCumul[100100], costMinCumul2[100100];
void cumulB(int pos) {
done[pos] = true;
costMinCumul[pos] = costMinB[pos];
for(int loop = 0; loop < minGraph[pos].size(); ++loop) {
if(!done[minGraph[pos][loop].end]) {
cumulB(minGraph[pos][loop].end);
}
costMinCumul[pos] = min(costMinCumul[minGraph[pos][loop].end], costMinCumul[pos]);
}
}
vector<vector<Vertice>> inverse() {
vector<vector<Vertice>> inv(100100);
for(int loop = 0; loop < 100100; ++loop) {
for(int looping = 0; looping < minGraph[loop].size(); ++looping) {
inv[minGraph[loop][looping].end].push_back({minGraph[loop][looping].end, loop, minGraph[loop][looping].cost});
}
}
return inv;
}
void cumulB2(int pos) {
costMinCumul2[pos] = costMinB[pos];
for(int loop = 0; loop < minGraph[pos].size(); ++loop) {
if(done[minGraph[pos][loop].end]) {
if(costMinCumul2[minGraph[pos][loop].end] == 2e18) {
cumulB2(minGraph[pos][loop].end);
}
costMinCumul2[pos] = min(costMinCumul2[pos], costMinCumul2[minGraph[pos][loop].end]);
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int nbVilles, nbRoutes, start, end, bookA, bookB;
cin >> nbVilles >> nbRoutes >> start >> end >> bookA >> bookB;
start--;end--;bookA--;bookB--;
for(int loop = 0; loop < nbRoutes; ++loop) {
int nodeA, nodeB, cost;
cin >> nodeA >> nodeB >> cost;
nodeA--;nodeB--;
graph[nodeA].push_back({nodeA, nodeB, cost});
graph[nodeB].push_back({nodeB, nodeA, cost});
}
priority_queue<Vertice, vector<Vertice>, compare> q;
q.push({-1, start, 0});
for(int loop = 0; loop < nbVilles; ++loop) {
done[loop] = false;
costMin[loop] = 2e18;
}
costMin[start] = 0;
while(q.size() > 0) {
Vertice enCours = q.top();
q.pop();
if(done[enCours.end]) {
continue;
}
done[enCours.end] = true;
for(int loop = 0; loop < graph[enCours.end].size(); ++loop) {
Vertice arrivee = graph[enCours.end][loop];
if(done[arrivee.end]) {
continue;
}
if(costMin[arrivee.end] == arrivee.cost + enCours.cost) {
minGraph[arrivee.end].push_back({arrivee.end, arrivee.start, 0});
}
else if(costMin[arrivee.end] > arrivee.cost + enCours.cost) {
minGraph[arrivee.end].clear();
minGraph[arrivee.end].push_back({arrivee.end, arrivee.start, 0});
costMin[arrivee.end] = arrivee.cost + enCours.cost;
q.push({arrivee.start, arrivee.end, costMin[arrivee.end]});
}
}
}
for(int loop = 0; loop < nbVilles; ++loop) {
done[loop] = false;
costMin[loop] = 2e18;
}
costMin[bookA] = 0;
q.push({-1, bookA, 0});
while(q.size() > 0) {
Vertice enCours = q.top();
q.pop();
if(done[enCours.end]) {
continue;
}
done[enCours.end] = true;
for(int loop = 0; loop < graph[enCours.end].size(); ++loop) {
Vertice arrivee = graph[enCours.end][loop];
if(done[arrivee.end]) {
continue;
}
if(costMin[arrivee.end] > enCours.cost + arrivee.cost) {
costMin[arrivee.end] = enCours.cost + arrivee.cost;
q.push({arrivee.start, arrivee.end, enCours.cost + arrivee.cost});
}
}
}
int mini = costMin[bookB];
for(int loop = 0; loop < nbVilles; ++loop) {
costMinA[loop] = 2e18;
costMinB[loop] = 2e18;
done[loop] = false;
}
costMinA[bookA] = 0;
costMinB[bookB] = 0;
q.push({-1, bookA, 0});
while(q.size() > 0) {
Vertice enCours = q.top();
q.pop();
if(done[enCours.end]) {
continue;
}
done[enCours.end] = true;
for(int loop = 0; loop < graph[enCours.end].size(); ++loop) {
Vertice arrivee = graph[enCours.end][loop];
if(done[arrivee.end]) {
continue;
}
if(costMinA[arrivee.end] > enCours.cost + arrivee.cost) {
costMinA[arrivee.end] = enCours.cost + arrivee.cost;
q.push({arrivee.start, arrivee.end, enCours.cost + arrivee.cost});
}
}
}
for(int loop = 0; loop < nbVilles; ++loop) {
done[loop] = false;
}
q.push({-1, bookB, 0});
while(q.size() > 0) {
Vertice enCours = q.top();
q.pop();
if(done[enCours.end]) {
continue;
}
done[enCours.end] = true;
for(int loop = 0; loop < graph[enCours.end].size(); ++loop) {
Vertice arrivee = graph[enCours.end][loop];
if(done[arrivee.end]) {
continue;
}
if(costMinB[arrivee.end] > enCours.cost + arrivee.cost) {
costMinB[arrivee.end] = enCours.cost + arrivee.cost;
q.push({arrivee.start, arrivee.end, enCours.cost + arrivee.cost});
}
}
}
for(int loop = 0; loop < nbVilles; ++loop) {
done[loop] = false;
}
for(int loop = 0; loop < nbVilles; ++loop) {
costMinCumul[loop] = 2e18;
costMinCumul2[loop] = 2e18;
}
cumulB(end);
minGraph = inverse();
cumulB2(start);
for(int loop = 0; loop < nbVilles; ++loop) {
if(done[loop]) {
mini = min(mini, costMinA[loop] + min(costMinCumul[loop], costMinCumul2[loop]));
}
}
cout << mini << '\n';
}
