#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pb push_back
#define fi first
#define se second
#define mp make_pair
const int mod = LLONG_MAX;
const int maxn = 1e5 + 5;
int n, m, s, t, u, v;
vector<pair<int, int>> adj[maxn];
vector<vector<int>> jalan;
void cari(int node, vector<int>& jalann, vector<int> parent[]){
if(node == -1){
jalan.pb(jalann);
return;
}
for(int par : parent[node]){
//cout << par << " par" << endl;
jalann.pb(node);
cari(par, jalann, parent);
jalann.pop_back();
}
}
int32_t main()
{
IOS
cin >> n >> m;
cin >> s >> t;
cin >> 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});
}
//pertama cari shortest path untuk dari s ke t
//problem = bgmn kalau ada lbh dari 1 path dan jaraknya sama
vector<int> d(n + 1, mod);
vector<int> p(n + 1, -1);
vector<int> vis(n + 1, 0);
//vector<int> jalan[n + 1];
vector<int> parent[n + 1];
d[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push({0, s});
parent[s] = {-1};
while(!q.empty()){
int v = q.top().se;
int vd = q.top().fi;
q.pop();
//cout << v << " v" << endl;
if(vd != d[v])continue;
for(auto i : adj[v]){
int to = i.fi;
int val = i.se;
//if(vis[to]) continue;
if(d[v] + val < d[to]){
d[to] = d[v] + val;
p[to] = v;
q.push({d[to], to});
parent[to].clear();
parent[to].pb(v);
}else if(d[v] + val == d[to]){
parent[to].pb(v);
}
}
}
vector<int> jalann;
cari(t, jalann, parent);
for(auto i : jalan){
reverse(i.begin(), i.end());
for(auto j : i){
cout << j << " ";
}cout << endl;
}
//we found multiple path
// vector<int> path;
// for(int i = t; i != s; i = p[i]){
// path.pb(i);
// }
// path.pb(s);
// reverse(path.begin(), path.end());
// for(auto i : path){
// cout << i << " ";
// }cout << endl;
// for(int i = 1; i < path.size(); i++){
// tanda[{path[i], path[i - 1]}] = true;
// tanda[{path[i - 1], path[i]}] = true;
// }
// for(auto i : tanda){
// cout << i << " ";
// }cout << endl;
int mini = LLONG_MAX;
for(auto i : jalan){
vector<int> d1(n + 1, mod);
vector<int> vis1(n + 1, 0);
vector<int> p1(n + 1, -1);
map<pair<int, int>, bool> tanda;
for(int j = 1; j < i.size(); j++){
tanda[{i[j], i[j - 1]}] = 1;
tanda[{i[j - 1], i[j]}] = 1;
}
d1[u] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q1;
q1.push({0, u});
while(!q1.empty()){
int v = q1.top().se;
int vd = q1.top().fi;
q1.pop();
//cout << v << " v" << endl;
if(vd != d1[v])continue;
for(auto i : adj[v]){
int to = i.fi;
int val = i.se;
if(tanda[{v, to}]) val = 0;
//if(vis[to]) continue;
if(d1[v] + val < d1[to]){
d1[to] = d1[v] + val;
p1[to] = v;
q1.push({d1[to], to});
}
}
}
mini = min(mini, d1[v]);
}
cout << mini << endl;
// vector<int> d1(n + 1, mod);
// vector<int> vis1(n + 1, 0);
// vector<int> p1(n + 1, -1);
// d1[u] = 0;
// priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q1;
// q1.push({0, u});
// while(!q1.empty()){
// int v = q1.top().se;
// int vd = q1.top().fi;
// q1.pop();
// //cout << v << " v" << endl;
// if(vd != d1[v])continue;
// for(auto i : adj[v]){
// int to = i.fi;
// int val = i.se;
// if(tanda[{v, to}]) val = 0;
// //if(vis[to]) continue;
// if(d1[v] + val < d1[to]){
// d1[to] = d1[v] + val;
// p1[to] = v;
// q1.push({d1[to], to});
// }
// }
// }
// for(int i = 1; i <= n; i++){
// d1[u] = 0;
// int v = -1;
// for(int j = 1; j <= n; j++){
// if(!vis1[j] && (v == -1 || d1[j] < d1[v])){
// v = j;
// }
// }
// if(d1[v] == mod) break;
// vis1[v] = true;
// for(auto i : adj[v]){
// int to = i.fi;
// int val = i.se;
// if(tanda[{v, to}]){
// val = 0;
// }
// if(d1[v] + val < d1[to]){
// d1[to] = d1[v] + val;
// p[to] = v;
// }
// }
// }
// vector<int> ans;
// for(int i = v; i != u; i = p[i]){
// ans.pb(i);
// }ans.pb(u);
// reverse(ans.begin(), ans.end());
// for(auto i : ans){
// cout << i << " ";
// }cout << endl;
//cout << d1[v] << endl;
}
