#include <bits/stdc++.h>
#include <vector>
#include <tuple>
// #include "debugging.h"
// #include <atcoder/lazysegtree>
// #include <atcoder/dsu>
// #include <atcoder/segtree>
// #include <atcoder/modint>
// using namespace atcoder;
// using mint = static_modint<998244353>;
using namespace std;
const int LARGE = 1e9;
#define all(x) (x).begin(), (x).end()
using ll = long long;
typedef pair<ll, ll> pi;
// bool cmp(pair<ll, ll> a, pair<ll, ll> b)
// {
// if (a.second < b.second)
// return true;
// return false;
// }
// struct node
// {
// // part which will store data
// int data;
// // pointer to the previous node
// struct node *prev;
// // pointer to the next node
// struct node *next;
// };
const int MOD = 998244353;
// template<int MOD, int RT> struct mint {
// static const int mod = MOD;
// static constexpr mint rt() { return RT; } // primitive root
// int v;
// explicit operator int() const { return v; }
// mint():v(0) {}
// mint(ll _v):v(int(_v%MOD)) { v += (v<0)*MOD; }
// mint& operator+=(mint o) {
// if ((v += o.v) >= MOD) v -= MOD;
// return *this; }
// mint& operator-=(mint o) {
// if ((v -= o.v) < 0) v += MOD;
// return *this; }
// mint& operator*=(mint o) {
// v = int((ll)v*o.v%MOD); return *this; }
// friend mint pow(mint a, ll p) { assert(p >= 0);
// return p==0?1:pow(a*a,p/2)*(p&1?a:1); }
// friend mint inv(mint a) { assert(a.v != 0); return pow(a,MOD-2); }
// friend mint operator+(mint a, mint b) { return a += b; }
// friend mint operator-(mint a, mint b) { return a -= b; }
// friend mint operator*(mint a, mint b) { return a *= b; }
// };
// using mi = mint<(int)MOD, 5>;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
ll solve()
{
ll N, M;
cin >> N >> M;
ll s, t;
cin >> s >> t;
s--;
t--;
ll u, v;
cin >> u >> v;
u--;
v--;
vector<vector<pair<ll, ll>>> g(N, vector<pair<ll, ll>>(0));
for (int i = 0; i < M; i++)
{
ll a, b, c;
cin >> a >> b >> c;
a--;
b--;
g[a].push_back(make_pair(b, c));
g[b].push_back(make_pair(a, c));
}
vector<vector<ll>> nodePars(N, vector<ll>(0));
vector<ll> vis(N);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pq.push(make_pair(0, s));
vector<ll> costToNode(N, INT64_MAX);
while (!pq.empty())
{
auto [cost, node] = pq.top();
pq.pop();
if (costToNode[node] == -1)
continue;
costToNode[node] = -1;
for (auto [nei, c] : g[node])
{
if (cost + c < costToNode[nei])
{
costToNode[nei] = cost + c;
nodePars[nei].clear();
nodePars[nei].push_back(node);
}
else if (cost + c == costToNode[nei])
nodePars[nei].push_back(node);
pq.push(make_pair(cost + c, nei));
}
}
vector<ll> distU(N, INT64_MAX);
vector<ll> distV(N, INT64_MAX);
auto dijkstra = [&](ll u, vector<ll> &A)
{
pq.push(make_pair(0, u));
while (!pq.empty())
{
auto [cost, node] = pq.top();
pq.pop();
if (A[node] != INT64_MAX)
continue;
A[node] = cost;
for (auto [nei, c] : g[node])
{
pq.push(make_pair(cost + c, nei));
}
}
};
dijkstra(u, distU);
dijkstra(v, distV);
vector<ll> dpU(N, INT64_MAX);
vector<ll> dpV(N, INT64_MAX);
for (int i = 0; i < N; i++) {
dpU[i] = distU[i];
dpV[i] = distV[i];
}
ll ans = distU[v];
vector<ll> validNodes(N);
vector<ll> indeg(N);
vector<ll> st = {t};
while (!st.empty()) {
ll node = st.back();
st.pop_back();
validNodes[node] = 1;
for (auto nei : nodePars[node]) {
indeg[nei]++;
if (validNodes[nei]) continue;
validNodes[nei] = 1;
st.push_back(nei);
}
}
validNodes.clear();
validNodes.resize(N, 0);
vector<ll> bfs = {t};
while (!bfs.empty())
{
vector<ll> newbfs(0);
for (auto node : bfs)
{
ans = min(ans, dpU[node]+distV[node]);
ans = min(ans, dpV[node]+distU[node]);
validNodes[node] = 1;
for (auto par : nodePars[node])
{
dpU[par] = min(dpU[par], dpU[node]);
dpV[par] = min(dpV[par], dpV[node]);
indeg[par]--;
if (validNodes[par] || indeg[par] > 0)
continue;
validNodes[par] = 1;
newbfs.push_back(par);
}
}
bfs = newbfs;
}
cout << ans << '\n';
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("time.in", "r", stdin);
// freopen("time.out", "w", stdout);
// ll caseCnt = 1;
// ll T;
// cin >> T;
// while (T--)
// {
solve();
// cout << "Case #"<< caseCnt << ": " << ans << '\n';
// caseCnt++;
// }
return 0;
}
