#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct arbore {
int nod,cost;
bool operator>(arbore other)const {
return cost > other.cost;
}
};
struct arbore2 {
int nod,cost,stare;
};
int n,m,u,v,s,t;
int rez=1e9;
vector<vector<arbore>>tabel;
vector<vector<int>>drumuri;
vector<int>d;
void dij(int start,int sf) {
priority_queue<arbore,vector<arbore>,greater<arbore>>pq;
pq.push({start,0});
while(!pq.empty()) {
arbore curent = pq.top();
pq.pop();
if(d[curent.nod] < curent.cost)
continue;
for(auto i : tabel[curent.nod]) {
if(d[i.nod] > curent.cost + i.cost) {
d[i.nod] = curent.cost + i.cost;
pq.push({i.nod,d[i.nod]});
}
}
}
}
void rec(int start,int sf) {
queue<arbore2>q;
int mx=0;
drumuri[0].push_back(start);
q.push({start,d[start],0});
while(!q.empty()) {
arbore2 curent = q.front();
q.pop();
if(curent.nod == sf)
continue;
int cnt= 0;
for(auto i : tabel[curent.nod]) {
if(d[i.nod] == curent.cost - i.cost) {
if(cnt == 0) {
drumuri[curent.stare].push_back(i.nod);
q.push({i.nod,d[i.nod],curent.stare});
cnt++;
mx = max(mx,curent.stare);
} else {
int nou = mx + 1;
drumuri[nou] = drumuri[curent.stare];
drumuri[nou].push_back(i.nod);
cnt++;
q.push({i.nod,d[i.nod],nou});
mx = max(mx,nou);
}
}
}
}
}
void calc(vector<vector<arbore>>&tabel2) {
priority_queue<arbore,vector<arbore>,greater<arbore>>pq;
vector<int>di(n+1,1e9);
pq.push({u,0});
di[u]=0;
while(!pq.empty()) {
arbore curent = pq.top();
pq.pop();
if(di[curent.nod] < curent.cost)
continue;
for(auto i : tabel2[curent.nod]) {
if(di[i.nod] > curent.cost + i.cost) {
di[i.nod] = curent.cost + i.cost;
pq.push({i.nod,di[i.nod]});
}
}
}
rez = min(rez,di[v]);
}
int main() {
cin>>n>>m>>s>>t>>u>>v;
tabel.resize(n+1);
d.resize(n+1,1e9);
drumuri.resize(n+1);
for(int i=1; i<=m; i++) {
int a,b,c;
cin>>a>>b>>c;
tabel[a].push_back({b,c});
tabel[b].push_back({a,c});
}
/// dist de la s la t
dij(s,t);
/// reconstruiesc
rec(t,s);
///verific
for(auto i : drumuri){
cout<<endl;
for(auto j : i)
cout<<j<<" ";
}
for(int i=0;i<drumuri.size();i++){
if(drumuri[i].size() == 0)
break;
vector<vector<arbore>>nou = tabel;
for(int j=0;j<drumuri[i].size()-1;j++){
nou[drumuri[i][j]].push_back({drumuri[i][j+1],0});
nou[drumuri[i][j+1]].push_back({drumuri[i][j],0});
}
calc(nou);
}
cout<<rez;
return 0;
}
