#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "commuter"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 3e5 + 9;
int n, m;
int s1, s2;
int source, destination;
iii edge[MAXN];
vector<int> g[MAXN];
vector<int> traceback[MAXN];
vector<int> SPG[MAXN]; //shortest path graph
int dist[2][MAXN], distStation[MAXN], visited[MAXN];
void dijkstra(int s, int dist[]){
dist[s] = 0;
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, s});
while(!pq.empty()){
int du = pq.top().fi;
int u = pq.top().se;
pq.pop();
if (du > dist[u]) continue;
for(auto id: g[u]){
int v = edge[id].se.fi + edge[id].se.se - u;
int w = edge[id].fi;
if (minimize(dist[v], dist[u] + w)){
pq.push({dist[v], v});
}
}
}
}
void buildDijkstra(int s1){
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, s1});
distStation[s1] = 0;
while(!pq.empty()){
int du = pq.top().fi;
int u = pq.top().se;
pq.pop();
for(auto id: g[u]){
int v = edge[id].se.fi + edge[id].se.se- u;
int w = edge[id].fi;
if (minimize(distStation[v], distStation[u] + w)){
pq.push({distStation[v], v});
traceback[v].clear();
traceback[v].pb(id);
}
else if (distStation[v] == distStation[u] + w){
traceback[v].pb(id);
}
}
}
queue<int> q;
q.push(s2);
visited[s2] = true;
while(!q.empty()){
int u = q.front();
q.pop();
for(auto id: traceback[u]){
int v = edge[id].se.fi + edge[id].se.se - u;
SPG[v].pb(id);
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
int dp1[MAXN], dp2[MAXN], ans = inf; //dist_x_dest be nhat den duoc.
int solve1(int u){
if (dp1[u] != -1) return dp1[u];
dp1[u] = dist[1][u];
for(auto id: SPG[u]){
int v = edge[id].se.fi + edge[id].se.se - u;
minimize(ans, dist[0][u] + solve1(v));
minimize(dp1[u], solve1(v));
}
return dp1[u];
}
int solve2(int u){
if (dp2[u] != -1) return dp2[u];
dp2[u] = dist[0][u];
for(auto id: SPG[u]){
int v = edge[id].se.fi + edge[id].se.se - u;
minimize(ans, dist[1][u] + solve2(v));
minimize(dp2[u], solve2(v));
}
return dp2[u];
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> n >> m;
cin >> s1 >> s2;
cin >> source >> destination;
FOR(i, 1, m){
int a, b, w;
cin >> a >> b >> w;
edge[i] = {w, {a, b}};
g[a].pb(i);
g[b].pb(i);
}
memset(dp1, -1, sizeof(dp1));
memset(visited, false, sizeof(visited));
memset(dist, 0x3f, sizeof(dist));
memset(distStation, 0x3f, sizeof(distStation));
memset(dp2, -1, sizeof(dp2));
dijkstra(source, dist[0]);
dijkstra(destination, dist[1]);
buildDijkstra(s1);
ans = dist[0][destination];
solve1(s1);
solve2(s1);
cout << ans << endl;
}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/
