/**
* The 17th Japanese Olympiad in Informatics (2018) - Final Round
* Problem: Commuter Pass
* (https://oj.uz/problem/view/JOI18_commuter_pass)
*
* Solution author: hiereneko
*
* Approach:
* - ...
**/
#include "bits/stdc++.h"
using namespace std;
using lint = long long;
#define IN "iii.txt"
#define OUT "ooo.txt"
#define MULTI_TEST false
constexpr int MAX = 1e9 + 5;
constexpr lint LMAX = 1e18 + 5;
void solve() {
int n, m;
cin >> n >> m;
int s1, f1, s2, f2; /// start, finish
cin >> s1 >> f1 >> s2 >> f2;
vector<vector<pair<int, lint>>> g(n + 1);
for (int i = 0, u, v, w; i < m; i++) {
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
auto dijkstra = [&](int s) -> vector<lint> {
vector<lint> dist(n + 1, LMAX);
dist[s] = 0;
priority_queue<pair<lint, int>,
vector<pair<lint, int>>,
greater<pair<lint, int>>> q;
q.push({0ll, s});
while (q.size()) {
lint d = q.top().first;
int u = q.top().second;
q.pop();
if (d > dist[u]) {
continue;
}
for (const auto& p : g[u]) {
int v = p.first;
lint w = p.second;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
q.push({dist[v], v});
}
}
}
return dist;
};
vector<lint> dist_s1 = dijkstra(s1);
vector<lint> dist_f1 = dijkstra(f1);
vector<lint> dist_s2 = dijkstra(s2);
vector<lint> dist_f2 = dijkstra(f2);
lint ans = dist_s2[f2];
/// put all vertices belong to any shortest s1-f1 path in a DAG
vector<int> dag(n);
iota(begin(dag), end(dag), 1);
sort(begin(dag), end(dag), [&](const auto& lhs, const auto& rhs) {
return dist_s1[lhs] < dist_s1[rhs];
});
vector<lint> dp_s2(n + 1, LMAX);
vector<lint> dp_f2(n + 1, LMAX);
for (int u : dag) {
if (dist_s1[u] + dist_f1[u] != dist_s1[f1]) {
continue;
}
/// only process vertices that is in the shortest s1-f1 path
dp_s2[u] = dist_s2[u];
dp_f2[u] = dist_f2[u];
for (const auto& p : g[u]) {
int v = p.first;
lint w = p.second;
if (dist_s1[v] + w == dist_s1[u]) {
dp_s2[u] = min(dp_s2[u], dp_s2[v]);
dp_f2[u] = min(dp_f2[u], dp_f2[v]);
}
}
ans = min(ans, dist_s2[u] + dp_f2[u]);
ans = min(ans, dist_f2[u] + dp_s2[u]);
}
cout << ans;
}
signed main() {
if (fopen(IN, "r")) {
freopen(IN, "r", stdin);
freopen(OUT, "w", stdout);
}
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
if (MULTI_TEST) { cin >> t; }
for (int tc = 1; tc <= t; tc++) {
if (MULTI_TEST) { cout << "Test case #" << tc << ":\n"; }
solve();
if (MULTI_TEST) { cout << '\n'; }
}
if (MULTI_TEST) { cout << 1000.0 * clock() / CLOCKS_PER_SEC << " ms"; }
return 0;
}
/**
--------------------------------------------------
X INPUT X
--------------------------------------------------
5
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
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
5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10
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
--------------------------------------------------
X OUTPUT X
--------------------------------------------------
2
3000000000
15
0
19
**/
