#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define pb push_back
vector<vector<pair<int, int>>> adj;
int ans;
int s, t;
vector<int> dis;
vector<int> dis2;
vector<int> dis3;
vector<bool> can;
void dfs(int node, int mn1, int mn2) {
ans = min(ans, mn1 + mn2);
if(node == s) return;
for(auto &[a, b] : adj[node]) {
if(dis[a] + b == dis[node]) {
dfs(a, min(mn1, dis2[a]), min(mn2, dis3[a]));
}
}
}
void solve() {
int n, m;
cin >> n >> m;
int u, v;
adj.assign(n + 1, {});
dis.assign(n + 1, -1);
dis2.assign(n + 1, -1);
dis3.assign(n + 1, -1);
can.assign(n + 1, 0);
cin >> s >> t >> u >> v;
for(int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
adj[a].pb({b, c});
adj[b].pb({a, c});
}
priority_queue<pair<int, int>> q;
queue<int> p;
q.push({0, s});
while(!q.empty()) {
int u = q.top().ss;
int t = q.top().ff;
q.pop();
if(dis[u] != -1) continue;
dis[u] = -t;
for(auto &[a, b] : adj[u]) {
if(dis[a] == -1) q.push({t - b, a});
}
}
q.push({0, v});
while(!q.empty()) {
int u = q.top().ss;
int t = q.top().ff;
q.pop();
if(dis2[u] != -1) continue;
dis2[u] = -t;
for(auto &[a, b] : adj[u]) {
if(dis2[a] == -1) q.push({t - b, a});
}
}
q.push({0, u});
while(!q.empty()) {
int u = q.top().ss;
int t = q.top().ff;
q.pop();
if(dis3[u] != -1) continue;
dis3[u] = -t;
for(auto &[a, b] : adj[u]) {
if(dis3[a] == -1) q.push({t - b, a});
}
}
ans = dis2[u];
can[t] = 1;
p.push(t);
while(!p.empty()) {
int u = p.front(); p.pop();
for(auto &[a, b] : adj[u]) {
if(!can[a] && dis[a] + b == dis[u]) {
can[a] = 1;
p.push(a);
}
}
}
vector<int> ind1(n + 1, 0);
vector<int> ind2(n + 1, 0);
for(int i = 1; i <= n; i++) {
if(!can[i]) continue;
for(auto &[a, b] : adj[i]) {
if(can[a]) {
if(dis[a] + b == dis[i]) ind1[i]++;
else {
ind2[i]++;
assert(dis[i] + b == dis[a]);
}
}
}
}
vector<int> dpu1(n + 1, 1e18);
vector<int> dpv1(n + 1, 1e18);
vector<int> dpu2(n + 1, 1e18);
vector<int> dpv2(n + 1, 1e18);
for(int i = 1; i <= n; i++) {
if(can[i] && !ind1[i]) p.push(i);
}
while(!p.empty()) {
int u = p.front(); p.pop();
cout << u << "\n";
dpu1[u] = min(dpu1[u], dis2[u]);
dpv1[u] = min(dpv1[u], dis3[u]);
for(auto &[a, b] : adj[u]) {
if(can[a] && dis[u] + b == dis[a]) {
ind1[a]--;
if(ind1[a] == 0) {
p.push(a);
dpu1[a] = min(dpu1[a], dpu1[u]);
dpv1[a] = min(dpv1[a], dpv1[u]);
}
}
}
}
for(int i = 1; i <= n; i++) {
if(can[i] && !ind2[i]) p.push(i);
}
while(!p.empty()) {
int u = p.front(); p.pop();
// cout << u << "\n";
dpu2[u] = min(dpu2[u], dis2[u]);
dpv2[u] = min(dpv2[u], dis3[u]);
for(auto &[a, b] : adj[u]) {
if(can[a] && dis[a] + b == dis[u]) {
ind2[a]--;
if(ind2[a] == 0) {
p.push(a);
dpu2[a] = min(dpu2[a], dpu2[u]);
dpv2[a] = min(dpv2[a], dpv2[u]);
}
}
}
}
for(int i = 1; i <= n; i++) {
if(can[i]) {
ans = min({ans, dpu1[i] + dpv2[i], dpu2[i] + dpv1[i]});
// cout << dis3[i] << " ";
// cout << dpv1[i] << "\n";
}
}
cout << ans << "\n";
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
