#include<bits/stdc++.h>
#ifdef _DEBUG
#define ls(x) << x << ", "
#define lv(x) << #x << ": " << flush << x << ", "
#define pr(x) cout << "Line: " << __LINE__ << ", " x << endl;
#else
#define ls(x)
#define lv(x)
#define pr(x) ;
#endif
using namespace std;
typedef unsigned int uint;
typedef unsigned long long ull;
struct Edge {
uint to;
ull cost;
Edge() {}
Edge(uint to, ull cost) : to(to), cost(cost) {}
};
struct Vert {
uint i;
ull cost;
Vert() {};
Vert(uint i, ull cost) : i(i), cost(cost) {};
};
bool operator>(const Vert& a, const Vert& b) {
return a.cost > b.cost;
}
constexpr ull ll_inf = 1e14;
void djikstra(uint r, uint n, const vector<vector<Edge>>& g,
vector<uint> &orig, vector<ull>& cost) {
orig.resize(n);
cost.resize(n);
fill(cost.begin(), cost.end(), ll_inf);
fill(orig.begin(), orig.end(), n);
priority_queue<Vert, vector<Vert>, greater<Vert>> q;
q.push(Vert(r, 0));
cost[r] = 0;
orig[r] = 0;
while (!q.empty()) {
Vert vv = q.top();
uint v = vv.i;
pr(ls("visit") lv(v) lv(vv.cost) lv(cost[v]))
q.pop();
if (cost[v] < vv.cost) {
// better path was found later
continue;
}
for (uint i = 0; i < g[v].size(); i++) {
Edge e = g[v][i];
uint k = e.to;
pr(lv(i) lv(e.to) lv(e.cost))
if (cost[k] > cost[v] + e.cost) {
cost[k] = cost[v] + e.cost;
orig[k] = v;
pr(ls("neighbour") lv(v) lv(k) lv(e.cost) lv(cost[k]));
q.push(Vert(k, cost[k]));
}
}
}
pr(ls("end"))
}
void bfs(uint r, uint w, uint n, const vector<vector<uint>>& g, vector<bool>& visited) {
visited.resize(n);
fill(visited.begin(), visited.end(), false);
stack<uint> st;
st.push(r);
visited[r] = true;
visited[w] = true; // do not enter
pr(ls("in") lv(r))
while (!st.empty()) {
uint v = st.top();
st.pop();
for (uint x: g[v]) {
if (!visited[x]) {
visited[x] = true;
pr(ls("in") lv(v) lv(x))
st.push(x);
}
}
}
}
vector<bool> make_on_path(uint s, uint t, uint n, const vector<vector<Edge>>& g) {
vector<uint> orig;
vector<ull> cost;
djikstra(s, n, g, orig, cost);
vector<vector<uint>> r_orig(n, vector<uint>());
for (uint i = 0; i < n; i++) {
pr(lv(i) lv(orig[i]))
r_orig[orig[i]].push_back(i);
}
vector<bool> is_on_path;
bfs(s, t, n, r_orig, is_on_path);
for (uint i = 0; i < n; i++) {
pr(lv(i) lv(is_on_path[i]))
}
djikstra(t, n, g, orig, cost);
fill(r_orig.begin(), r_orig.end(), vector<uint>());
for (uint i = 0; i < n; i++) {
r_orig[orig[i]].push_back(i);
}
vector<bool> is_on_t;
bfs(t, s, n, r_orig, is_on_t);
for (uint i = 0; i < n; i++) {
if (!is_on_t[i]) {
is_on_path[i] = false;
}
}
return is_on_path;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
uint n, m, s, t, u, v;
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
s--;
t--;
u--;
v--;
pr(lv(s) lv(t) lv(u) lv(v))
vector<vector<Edge>> g(n, vector<Edge>());
for (uint i = 0; i < m; i++) {
uint a, b;
ull c;
cin >> a >> b >> c;
a--;
b--;
pr(ls(a) ls("->") ls(b))
g[a].push_back(Edge(b, c));
g[b].push_back(Edge(a, c));
}
vector<bool> on_path = make_on_path(s, t, n, g);
for (uint i = 0; i < n; i++) {
pr(lv(i) lv(on_path[i]))
}
vector<uint> orig;
vector<ull> cost;
djikstra(u, n, g, orig, cost);
ull cost_to_v = cost[v];
ull cost_to_path = ll_inf;
for (uint i = 0; i < n; i++) {
if (!on_path[i]) continue;
pr(lv(i) lv(cost[i]))
cost_to_path = min(cost_to_path, cost[i]);
}
djikstra(v, n, g, orig, cost);
ull cost_from_path = ll_inf;
for (uint i = 0; i < n; i++) {
if (!on_path[i]) continue;
cost_from_path = min(cost_from_path, cost[i]);
}
ull min_cost = min(cost_from_path + cost_to_path, cost_to_v);
pr(lv(min_cost) lv(cost_from_path) lv(cost_to_path) lv(cost_to_v))
cout << min_cost << '\n';
}
