#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18;
// ------------------------------------------------------------
// Fast Dijkstra (min-heap, no recursion)
// ------------------------------------------------------------
pair<vector<ll>, vector<vector<int>>> dijkstra_with_par(int n,
const vector<vector<pair<int,ll>>> &adj, int src)
{
vector<ll> dist(n, INF);
vector<vector<int>> par(n);
dist[src] = 0;
priority_queue<
pair<ll,int>,
vector<pair<ll,int>>,
greater<pair<ll,int>>
> pq;
pq.emplace(0, src);
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d != dist[u]) continue;
for (auto &e : adj[u]) {
int v = e.first;
ll w = e.second;
ll nd = d + w;
if (dist[v] > nd) {
dist[v] = nd;
par[v].clear();
par[v].push_back(u);
pq.emplace(nd, v);
} else if (dist[v] == nd) {
par[v].push_back(u);
}
}
}
return {dist, par};
}
// ------------------------------------------------------------
// Faster Dijkstra (no parent collection)
// ------------------------------------------------------------
vector<ll> dijkstra(int n, const vector<vector<pair<int,ll>>> &adj, int src)
{
vector<ll> dist(n, INF);
dist[src] = 0;
priority_queue<
pair<ll,int>,
vector<pair<ll,int>>,
greater<pair<ll,int>>
> pq;
pq.emplace(0, src);
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d != dist[u]) continue;
for (auto &e : adj[u]) {
int v = e.first;
ll w = e.second;
ll nd = d + w;
if (dist[v] > nd) {
dist[v] = nd;
pq.emplace(nd, v);
}
}
}
return dist;
}
// ------------------------------------------------------------
// Main solve
// ------------------------------------------------------------
void solve() {
int n, m, s, t, u, v;
cin >> n >> m;
cin >> s >> t >> u >> v;
s--, t--, u--, v--;
vector<vector<pair<int,ll>>> adj(n);
for (int i = 0; i < m; i++) {
int a, b;
ll c;
cin >> a >> b >> c;
a--, b--;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
// Run Dijkstra
auto [dists, par] = dijkstra_with_par(n, adj, s);
vector<ll> distu = dijkstra(n, adj, u);
vector<ll> distv = dijkstra(n, adj, v);
// Build shortest-path DAG from s to t
vector<vector<int>> dag(n);
// stack DFS (reverse parent edges)
vector<char> used(n, 0);
stack<int> st;
st.push(t);
used[t] = 1;
while (!st.empty()) {
int x = st.top(); st.pop();
for (int p : par[x]) {
dag[p].push_back(x);
if (!used[p]) {
used[p] = 1;
st.push(p);
}
}
}
// Traverse DAG from s and compute answer
ll ans = INF;
stack<tuple<int,ll,ll>> dfsstack;
dfsstack.emplace(s, INF, INF);
while (!dfsstack.empty()) {
auto [x, ud, vd] = dfsstack.top();
dfsstack.pop();
ud = min(ud, distu[x]);
vd = min(vd, distv[x]);
ans = min(ans, ud + vd);
for (int nx : dag[x])
dfsstack.emplace(nx, ud, vd);
}
ans = min(ans, distv[u]);
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
