// barkolorious - 08 December 2024
// in god, do we trust?
#include <bits/stdc++.h>
using namespace std;
#define FIN(x) freopen(x ".in", "r", stdin)
#define FOUT(x) freopen(x ".out", "w", stdout)
#define all(v) (v).begin(), (v).end()
#define int long long
#define pb push_back
#define sz size
#define fr first
#define sc second
#define __ << " " <<
const int N = 2e5 + 5;
int distU[N], distV[N], distS[N], dpU[N], dpV[N];
vector<pair<int, int>> adj[N];
int vis[N], ans;
void dijsktra1 (int root, int dist[]) {
fill(vis, vis + N, false);
priority_queue<pair<int, int>> pq;
pq.push({0, root});
while (!pq.empty()) {
int d = pq.top().fr, u = pq.top().sc;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
dist[u] = -d;
// cout << u __ -d << endl;
for (auto edge : adj[u]) {
int v = edge.fr, w = edge.sc;
pq.push({d - w, v});
}
}
}
void dijsktra2 (int start, int end) {
fill(vis, vis + N, false);
fill(dpU, dpU + N, 1e15);
fill(dpV, dpV + N, 1e15);
priority_queue<pair<int, pair<int, int>>> pq;
pq.push({0, {start, 0}});
dpU[0] = dpV[0] = 1e15;
while (!pq.empty()) {
int d, u, par;
pair<int, int> p;
tie(d, p) = pq.top();
tie(u, par) = p;
pq.pop();
if (!vis[u]) {
vis[u] = true;
distS[u] = -d;
dpU[u] = min(distU[u], dpU[par]);
dpV[u] = min(distV[u], dpV[par]);
for (auto edge : adj[u]) {
int v = edge.fr, w = edge.sc;
pq.push({d - w, {v, u}});
}
} else if (-d == distS[u]) {
if (min(distU[u], dpU[par]) + min(distV[u], dpV[par]) <= dpU[u] + dpV[u]) {
dpU[u] = min(distU[u], dpU[par]);
dpV[u] = min(distV[u], dpV[par]);
}
}
}
ans = min(ans, dpU[end] + dpV[end]);
}
void solve () {
int n, m; cin >> n >> m;
int S, T, U, V; cin >> S >> T >> U >> V;
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
dijsktra1(U, distU);
dijsktra1(V, distV);
ans = distU[V];
dijsktra2(S, T);
dijsktra2(T, S);
cout << ans << endl;
}
/*
-- Sample 1 --
Input:
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
Output:
2
-- Sample 2 --
Input:
6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
Output:
3000000000
-- Sample 3 --
Input:
8 8
5 7
6 8
1 2 2
2 3 3
3 4 4
1 4 1
1 5 5
2 6 6
3 7 7
4 8 8
Output:
15
-- Sample 4 --
Input:
5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10
Output:
0
-- Sample 5 --
Input:
10 15
6 8
7 9
2 7 12
8 10 17
1 3 1
3 8 14
5 7 15
2 3 7
1 10 14
3 6 12
1 5 10
8 9 1
2 9 7
1 4 1
1 8 1
2 4 7
5 6 16
Output:
19
*/
/*
g++ -std=c++17 -O2 -Wall -DLOCAL "C:\Users\LENOVO\Desktop\BARKIN\Genel\Programming\Competitive\Questions\Olympiads\JOI18\JOI18_commuter_pass.cpp" -o _run
*/
int32_t main () {
#ifndef LOCAL
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#endif
#ifdef LOCAL
clock_t __START__ = clock();
FILE* __FILE_IN__ = FIN("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
FILE* __FILE_OUT__ = FOUT("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
#endif
solve();
#ifdef LOCAL
fclose(__FILE_IN__);
fclose(__FILE_OUT__);
cerr << "Executed in: " << fixed << setprecision(3) << (double) (clock() - __START__) / CLOCKS_PER_SEC << "seconds" << endl;
#endif
return 0;
}
