#include <bits/stdc++.h>
#define ll long long int
using namespace std;
const int MAXN = 1e5 + 10;
const int INF = INT_MAX;
const long long LINF = LLONG_MAX;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
vector<pair<int, ll>> adj[MAXN];
ll d[MAXN];
ll d2[MAXN];
ll dcomp1[MAXN];
ll dcomp2[MAXN];
bool visited[MAXN];
void dijkstra(int s) {
for(int i = 0; i < MAXN; i++){
d[i] = LINF;
d2[i] = LINF;
}
using pii = pair<
pair<ll, ll>,
pair<
pair<ll, ll>,
ll
>
>;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push(
{
{
0, dcomp1[s] + dcomp2[s]
},
{
{dcomp1[s], dcomp2[s]},
s
}
}
);
d[s] = 0;
d2[s] = dcomp1[s] + dcomp2[s] ;
while (!q.empty()) {
ll v = q.top().second.second;
ll d_v = q.top().first.first;
ll dc1 = q.top().second.first.first;
ll dc2 = q.top().second.first.second;
ll dcsum = q.top().first.second;
// cerr << d_v << " " << dcsum << " " << dc1 << " " << dc2 << " " << v << endl;
q.pop();
if (visited[v])
continue;
visited[v] = true;
// cerr << v << endl;
for (auto edge : adj[v]) {
ll to = edge.first;
ll len = edge.second;
ll now_dc1 = min(dc1, min(dcomp1[v], dcomp1[to]));
ll now_dc2 = min(dc2, min(dcomp2[v], dcomp2[to]));
if (d[v] + len < d[to]) {
d[to] = d[v] + len;
d2[to] = now_dc1 + now_dc2;
// q.push({d[to], to});
q.push(
{
{
d[to], now_dc1 + now_dc2
},
{
{now_dc1, now_dc2},
to
}
}
);
}else if(d[v] + len == d[to]){
if(now_dc1 + now_dc2 < d2[to]){
d2[to] = min(d2[to], now_dc1 + now_dc2);
q.push(
{
{
d[to], now_dc1 + now_dc2
},
{
{now_dc1, now_dc2},
to
}
}
);
}
}
}
}
}
void dijkstra_comp1(int s) {
for(int i = 0; i < MAXN; i++){
dcomp1[i] = LINF;
}
dcomp1[s] = 0;
using pii = pair<ll, int>;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push({0, s});
while (!q.empty()) {
int v = q.top().second;
ll d_v = q.top().first;
q.pop();
if (d_v != dcomp1[v])
continue;
for (auto edge : adj[v]) {
int to = edge.first;
ll len = edge.second;
if (dcomp1[v] + len < dcomp1[to]) {
dcomp1[to] = dcomp1[v] + len;
q.push({dcomp1[to], to});
}
}
}
}
void dijkstra_comp2(int s) {
for(int i = 0; i < MAXN; i++){
dcomp2[i] = LINF;
}
dcomp2[s] = 0;
using pii = pair<ll, int>;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push({0, s});
while (!q.empty()) {
int v = q.top().second;
ll d_v = q.top().first;
q.pop();
if (d_v != dcomp2[v])
continue;
for (auto edge : adj[v]) {
int to = edge.first;
ll len = edge.second;
if (dcomp2[v] + len < dcomp2[to]) {
dcomp2[to] = dcomp2[v] + len;
q.push({dcomp2[to], to});
}
}
}
}
void solv(){
int n, m;
cin >> n >> m;
int ibukota1, ibukota2;
cin >> ibukota1 >> ibukota2;
int comp1, comp2;
cin >> comp1 >> comp2;
for(int i = 0; i < m; i++){
ll u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dijkstra_comp1(comp1);
dijkstra_comp2(comp2);
dijkstra(ibukota1) ;
// cerr << d[ibukota2] << endl;
// cout << d2[ibukota2] << endl;
ll ans = min(d2[ibukota2], dcomp1[comp2]);
cout << ans << endl;
}
int main(){
int tc = 1;
// cin >> tc;
while(tc--)solv();
return 0;
}
