// Src : Vux2Code
/* Note :
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> lll;
#define fi first
#define se second
#define pusb push_back
#define popb pop_back
#define pusf push_front
#define popf pop_front
#define vec3d vector<vector<vector<ll>>>
#define vec2d vector<vector<ll>>
#define vec1d vector<ll>
vec3d set3 (ll x, ll y, ll z, ll val = 0) {return vec3d (x, vec2d (y, vec1d (z, val)));}
vec2d set2 (ll x, ll y, ll val = 0) {return vec2d (x, vec1d (y, val));}
// debug (+20)
#define debug(...) debug_impl(#__VA_ARGS__, __VA_ARGS__)
template<typename... Args>
void debug_impl(const char* names, Args&&... args) {
vector<string> _names;
{
istringstream ss(names);
string token;
while (getline(ss, token, ',')) {
auto l = token.find_first_not_of(" \t");
auto r = token.find_last_not_of(" \t");
if (l == string::npos) _names.push_back("");
else _names.push_back(token.substr(l, r - l + 1));
}
}
cerr << "(";
size_t _i = 0;
int _dummy[] = { 0, ((cerr << _names[_i] << " : " << args << (++_i < _names.size() ? ", " : "")), 0)... };
(void)_dummy;
cerr << ")" << endl;
}
// handy for loops
#define forinc(i, a, b) for (ll i = (a); i <= (b); ++i)
#define fordec(i, a, b) for (ll i = (a); i >= (b); --i)
#define foreach(i, j) for (ll i : (j))
#define all(a) (a).begin (), (a). end ()
#define uni(a) (a).erase(unique((a).begin(), (a). end ()), (a). end ())
const ll maxN = 1e6 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7;
void maxi(ll &x, ll y) { x = max(x, y); }
void mini(ll &x, ll y) { x = min(x, y); }
ll t = 1;
ll n, m, d1 [maxN], d2 [maxN] [3];
pll s1, s2;
vector <pll> adj [maxN];
vec1d trace [maxN];
priority_queue <pll, vector <pll>, greater <pll>> q;
priority_queue <lll, vector <lll>, greater <lll>> q3;
queue <ll> fq;
set <ll> mp1 [maxN], mp2 [maxN];
bool vst [maxN];
bool fin (set <ll> &x, ll y) {
return (x.find(y) == x.end());
}
void up (ll x, ll y, ll v) {
if (d2[x][y] > v) {
d2[x][y] = v;
q3.push({d2[x][y], {x, y}});
}
}
void solve() {
cin >> n >> m >> s1.fi >> s1.se >> s2.fi >> s2.se;
forinc(i, 1, m) {
ll a, b, c; cin >> a >> b >> c;
adj[a].pusb({b, c});
adj[b].pusb({a, c});
}
// 1. Dijkstra từ s1.fi, giữ trace các cha
memset(d1, 0x3f, sizeof d1);
d1[s1.fi] = 0;
q.push({0, s1.fi});
while (!q.empty()) {
auto [dist, u] = q.top(); q.pop();
if (dist != d1[u]) continue;
for (auto &e : adj[u]) {
ll v = e.fi, w = e.se;
if (d1[v] > dist + w) {
d1[v] = dist + w;
trace[v].clear();
trace[v].pusb(u);
q.push({d1[v], v});
} else if (d1[v] == dist + w) {
trace[v].pusb(u);
}
}
}
// 2. Xây mp1/mp2 cho mọi cạnh trên DAG (cung trên đường ngắn nhất)
// rồi BFS để tìm các đỉnh thực sự nằm trên DAG
forinc(i, 1, n) {
for (ll p : trace[i]) {
mp1[p].insert(i);
mp2[i].insert(p);
}
}
memset(vst, 0, sizeof vst);
fq.push(s1.se);
vst[s1.se] = true;
while (!fq.empty()) {
ll u = fq.front(); fq.pop();
for (ll p : trace[u]) {
// ghi nhận cung nếu chưa có, nhưng BFS qua đỉnh mỗi đỉnh một lần
if (!vst[p]) {
vst[p] = true;
fq.push(p);
}
}
}
ll ans = inf64;
// 3. Dijkstra đa trạng thái từ s2.fi
memset(d2, 0x3f, sizeof d2);
d2[s2.fi][0] = 0;
q3.push({0, {s2.fi, 0}});
while (!q3.empty()) {
auto [val, st] = q3.top(); q3.pop();
ll u = st.fi, sta = st.se;
if (val != d2[u][sta]) continue;
for (auto &e : adj[u]) {
ll v = e.fi, w = e.se;
bool isDAG = mp1[u].count(v) > 0;
if (isDAG) {
// miễn phí nếu đang state 0 hoặc 1
if (sta == 0 || sta == 1) up(v, 1, val);
else /* sta==2 */ up(v, 2, val + w);
} else {
ll cost = val + w;
if (sta == 0) up(v, 0, cost);
else up(v, 2, cost);
}
}
}
mini(ans, d2[s2.se][0]);
mini(ans, d2[s2.se][1]);
mini(ans, d2[s2.se][2]);
// 4. Lặp lại với hoán đổi s1.se <-> s1.fi (đảo chiều đường ngắn nhất)
memset(d2, 0x3f, sizeof d2);
d2[s2.fi][0] = 0;
q3.push({0, {s2.fi, 0}});
while (!q3.empty()) {
auto [val, st] = q3.top(); q3.pop();
ll u = st.fi, sta = st.se;
if (val != d2[u][sta]) continue;
for (auto &e : adj[u]) {
ll v = e.fi, w = e.se;
bool isDAG = mp2[u].count(v) > 0;
if (isDAG) {
if (sta == 0 || sta == 1) up(v, 1, val);
else up(v, 2, val + w);
} else {
ll cost = val + w;
if (sta == 0) up(v, 0, cost);
else up(v, 2, cost);
}
}
}
mini(ans, d2[s2.se][0]);
mini(ans, d2[s2.se][1]);
mini(ans, d2[s2.se][2]);
// So sánh với không dùng vé
// ... nếu cần, so sánh với khoảng cách trực tiếp
cout << ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
while (t--) solve();
return 0;
}
