// https://oj.uz/problem/view/JOI18_commuter_pass
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define INF INT64_MAX
typedef pair<int, int> Edge;
typedef pair<int, int> State;
typedef tuple<int, int, int, int, int> ModifiedState;
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
int s, t;
cin >> s >> t;
s--;
t--;
int u, v;
cin >> u >> v;
u--;
v--;
vector<set<Edge>> graph(n);
while (m--) {
int a, b, c;
cin >> a >> b >> c;
a--;
b--;
graph[a].insert({b, c});
graph[b].insert({a, c});
}
auto dijkstra = [&](int source) -> vector<int> {
vector<int> dist(n, INF);
dist[source] = 0;
priority_queue<State, vector<State>, greater<State>> pq;
pq.push({0, source});
while (pq.size()) {
auto [d, curr] = pq.top();
pq.pop();
if (d > dist[curr]) {
continue;
}
for (auto& [nei, cost] : graph[curr]) {
int new_cost = cost + d;
if (new_cost < dist[nei]) {
pq.push({new_cost, nei});
dist[nei] = new_cost;
}
}
}
return dist;
};
vector<int> dist_u = dijkstra(u);
vector<int> dist_v = dijkstra(v);
// Modified Dijkstra with state (best, min total penalty, min u penalthy, min v penalty, node)
priority_queue<ModifiedState, vector<ModifiedState>, greater<ModifiedState>> pq;
vector<pair<int, int>> dist(n, {INF, INF});
pq.push({0, dist_u[s] + dist_v[s], dist_u[s], dist_v[s], s});
while (pq.size()) {
auto [d, total_penalty, u_penalty, v_penalty, curr] = pq.top();
pq.pop();
if (pair<int, int>{d, total_penalty} > dist[curr]) {
continue;
}
for (auto& [nei, cost] : graph[curr]) {
int new_cost = cost + d;
int new_u_penalty = min(u_penalty, dist_u[nei]);
int new_v_penalty = min(v_penalty, dist_v[nei]);
int new_total_penalty = min(total_penalty, new_u_penalty + new_v_penalty);
if (pair<int, int>{new_cost, new_total_penalty} < dist[nei]) {
pq.push({new_cost, new_total_penalty, new_u_penalty, new_v_penalty, nei});
dist[nei] = {new_cost, new_total_penalty};
}
}
}
cout << min(dist[t].second, dist_u[v]) << '\n';
}
