#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
struct Arrete {
int debut, fin, cout;
bool sur_st = false;
};
vector<Arrete> arretes;
vector<vector<int>> stations;
int add_a(int a, int b, int c) {
arretes.push_back({a, b, c});
return arretes.size() - 1;
}
struct Pos {
int pos, etat;
bool operator<(const Pos& other) const {
return pos < other.pos;
}
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
int s, t, u, v;
cin >> s >> t >> u >> v;
s--;
t--;
u--;
v--;
stations.resize(n);
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
a--;
b--;
int num = add_a(a, b, c);
stations[a].push_back(num);
stations[b].push_back(num);
}
priority_queue<pair<int,int>> pq;
vector<int> profondeurs(n, INF);
pq.push({0, s});
while(!pq.empty()) {
int prof = -pq.top().first;
int pos = pq.top().second;
pq.pop();
if (profondeurs[pos] != INF) {
if (pos == t) break;
continue;
}
profondeurs[pos] = prof;
for (auto &&i: stations[pos]) {
pq.push(make_pair(- (arretes[i].cout + prof), arretes[i].debut + arretes[i].fin - pos));
}
}
vector<bool> vu(n, false);
vector<int> positions;
positions.push_back(t);
while (!positions.empty())
{
int pos = positions.back();
positions.pop_back();
if (vu[pos]) continue;
vu[pos] = true;
for (auto &&i: stations[pos]) {
int dest = arretes[i].debut + arretes[i].fin - pos;
if (profondeurs[dest] == profondeurs[pos] - arretes[i].cout) {
arretes[i].sur_st = true;
arretes[i].debut = dest;
arretes[i].fin = pos;
positions.push_back(dest);
}
}
}
priority_queue<pair<int, Pos>> file;
vector<vector<bool>> vus(4, vector<bool> (n, false));
file.push(make_pair(0, (Pos) {
u, 0
}));
while (!file.empty())
{
int prof = -file.top().first;
Pos pos = file.top().second;
file.pop();
if (vus[pos.etat][pos.pos]) {
continue;
}
if (pos.pos == v) {
cout << prof << endl;
return 0;
}
vus[pos.etat][pos.pos] = true;
for (auto &&i: stations[pos.pos]) {
if (arretes[i].sur_st) {
int etat = pos.etat;
if (pos.etat != 3) {
etat = 2;
if (pos.pos == arretes[i].debut) {
etat = 1;
}
if (pos.etat == 0 || pos.etat == etat) {
file.push(make_pair(-(prof), (Pos) {arretes[i].debut + arretes[i].fin - pos.pos, etat}));
}
}
}
int e = 0;
if (pos.etat != 0) {
e = 3;
}
file.push(make_pair(-(prof + arretes[i].cout), (Pos) {arretes[i].debut + arretes[i].fin - pos.pos, e}));
}
}
cerr << "EUH...\n";
return 0;
}
