#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long int ll;
ll inf = 1e18;
vector<vector<pair<int, int>>> adjList;
vector<vector<int>> DAG1, DAG2; // listas inversas de adyacencia
vector<ll> dist_desde_u, dist_hasta_v, dp_u, dp_v;
int n, s, t, u, v;
void dijkstra(int salida, vector<ll> & dist) {
dist.assign(n, inf);
priority_queue<pair<ll, int>> pq;
pq.push(make_pair(0, salida));
dist[salida] = 0;
while(!pq.empty()) {
ll distNodo = -pq.top().first;
int nodo = pq.top().second;
pq.pop();
if (dist[nodo] < distNodo) continue;
for (auto vecino: adjList[nodo]) {
int nodoVecino = vecino.first;
ll coste = vecino.second;
if (distNodo + coste < dist[nodoVecino]) {
dist[nodoVecino] = distNodo + coste;
pq.push(make_pair(-dist[nodoVecino], nodoVecino));
}
}
}
}
// coste minimo en llegar desde u al nodo
ll calcDPu(int nodo) {
if (dp_u[nodo] != -1) return dp_u[nodo];
ll ans = dist_desde_u[nodo];
for (int padre: DAG1[nodo]) {
ans = min(ans, calcDPu(padre));
}
return dp_u[nodo] = ans;
}
// coste minimo en llegar desde v al nodo
ll calcDPv(int nodo) {
if (dp_v[nodo] != -1) return dp_v[nodo];
ll ans = dist_hasta_v[nodo];
for (int padre: DAG2[nodo]) {
ans = min(ans, calcDPv(padre));
}
return dp_v[nodo] = ans;
}
ll minDist() {
vector<ll> dist_desde_s, dist_hasta_t;
dijkstra(s, dist_desde_s);
dijkstra(t, dist_hasta_t);
ll distanciaMasCorta = dist_desde_s[t];
DAG1.assign(n, vector<int>());
DAG2.assign(n, vector<int>());
for (int nodo = 0; nodo < n; nodo++) {
for (auto arista: adjList[nodo]) {
int vecino = arista.first;
ll coste = arista.second;
if (dist_desde_s[nodo] + coste + dist_hasta_t[vecino] == distanciaMasCorta) {
DAG1[vecino].push_back(nodo);
DAG2[nodo].push_back(vecino);
}
}
}
dijkstra(u, dist_desde_u);
dijkstra(v, dist_hasta_v);
ll ans = dist_desde_u[v];
dp_u.assign(n, -1);
dp_v.assign(n, -1);
for (int nodo = 0; nodo < n; nodo++) {
if (DAG1[nodo].size() + DAG2[nodo].size()) {
ans = min(ans, calcDPu(nodo) + calcDPv(nodo));
}
}
return ans;
}
int main() {
int m, a, b, c;
cin >> n >> m;
adjList.assign(n, vector<pair<int, int>>());
cin >> s >> t;
cin >> u >> v;
s--;
t--;
u--;
v--;
for (int i = 0; i < m; i++) {
cin >> a >> b >> c;
adjList[a-1].push_back(make_pair(b-1, c));
adjList[b-1].push_back(make_pair(a-1, c));
}
cout << minDist() << '\n';
return 0;
}
