#include <bits/stdc++.h>
using namespace std;
#define edge(xxxx,yyyy) ((xxxx)*(m+5)+(yyyy))
#define oo 1e18
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) (((xxxx)>>((aaaa)-1))&1)
#define totbit(xxxx) (32-__builtin_clz(xxxx))
#define totbitll(xxxx) (64-__builtin_clzll(ll(xxxx)))
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;
const ll base=333333349;
const ll mod=1e9+7;
const ld eps=1e-5;
const ll maxn=50009;
struct comp{
bool operator() (pll x,pll y) {
return x.se>y.se;
}
};
priority_queue<pll,vector<pll>,comp> heap;
ll dist[6][200009],n,m,s1,s2,t1,t2,i,res,u,v,w,antidistu[200009],distu[200009],distv[200009],antidistv[200009];
vector<pll> g[200009],antidag[200009],dag[200009];
void dijkstra(ll layer,ll source) {
for (ll ii=1;ii<=n;ii++) {
dist[layer][ii]=oo;
}
dist[layer][source]=0;
heap.push({source,0});
while (!heap.empty()) {
ll x=heap.top().fi;
ll y=heap.top().se;
heap.pop();
if (dist[layer][x]<y) continue;
for (pll ii:g[x]) {
if (dist[layer][ii.fi]>dist[layer][x]+ii.se) {
dist[layer][ii.fi]=dist[layer][x]+ii.se;
heap.push({ii.fi,dist[layer][ii.fi]});
}
}
}
}
int main(){
IO;
#ifndef ONLINE_JUDGE
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#else
#endif
cin>>n>>m;
cin>>s1>>t1;
cin>>s2>>t2;
for (i=1;i<=m;i++) {
cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dijkstra(1,s1);
dijkstra(2,t1);
dijkstra(3,s2);
dijkstra(4,t2);
/*
for (i=1;i<=n;i++) {
cout<<dist[1][i]<<' ';
}
cout<<'\n';
for (i=1;i<=n;i++) {
cout<<dist[2][i]<<' ';
}
cout<<'\n';
for (i=1;i<=n;i++) {
cout<<dist[3][i]<<' ';
}
cout<<'\n';
for (i=1;i<=n;i++) {
cout<<dist[4][i]<<' ';
}
cout<<'\n';
*/
for (i=1;i<=n;i++) {
distu[i]=oo;
distv[i]=oo;
antidistu[i]=oo;
antidistv[i]=oo;
}
for (i=1;i<=n;i++) {
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
for (pll ii:g[i]) {
if (dist[1][i]+ii.se+dist[2][ii.fi]==dist[1][t1]) {
dag[i].push_back({ii.fi,ii.se});
antidag[ii.fi].push_back({i,ii.se});
//cout<<"? "<<i<<' '<<ii.fi<<' '<<ii.se<<'\n';
}
}
}
for (i=1;i<=n;i++) {
//distu[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
distu[i]=dist[3][i];
for (pll ii:antidag[i]) {
distu[i]=min(distu[i],distu[ii.fi]);
}
for (pll ii:g[i]) {
distu[i]=min(distu[i],distu[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//distv[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
distv[i]=dist[4][i];
for (pll ii:dag[i]) {
distv[i]=min(distv[i],distv[ii.fi]);
}
for (pll ii:g[i]) {
distv[i]=min(distv[i],distv[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//antidistu[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
antidistu[i]=dist[3][i];
for (pll ii:dag[i]) {
antidistu[i]=min(antidistu[i],antidistu[ii.fi]);
}
for (pll ii:g[i]) {
antidistu[i]=min(antidistu[i],antidistu[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//antidistv[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
antidistv[i]=dist[4][i];
for (pll ii:antidag[i]) {
antidistv[i]=min(antidistv[i],antidistv[ii.fi]);
}
for (pll ii:g[i]) {
antidistv[i]=min(antidistv[i],antidistv[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//distu[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
distu[i]=dist[3][i];
for (pll ii:antidag[i]) {
distu[i]=min(distu[i],distu[ii.fi]);
}
for (pll ii:g[i]) {
distu[i]=min(distu[i],distu[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//distv[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
distv[i]=dist[4][i];
for (pll ii:dag[i]) {
distv[i]=min(distv[i],distv[ii.fi]);
}
for (pll ii:g[i]) {
distv[i]=min(distv[i],distv[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//antidistu[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
antidistu[i]=dist[3][i];
for (pll ii:dag[i]) {
antidistu[i]=min(antidistu[i],antidistu[ii.fi]);
}
for (pll ii:g[i]) {
antidistu[i]=min(antidistu[i],antidistu[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//antidistv[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
antidistv[i]=dist[4][i];
for (pll ii:antidag[i]) {
antidistv[i]=min(antidistv[i],antidistv[ii.fi]);
}
for (pll ii:g[i]) {
antidistv[i]=min(antidistv[i],antidistv[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//distu[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
distu[i]=dist[3][i];
for (pll ii:antidag[i]) {
distu[i]=min(distu[i],distu[ii.fi]);
}
for (pll ii:g[i]) {
distu[i]=min(distu[i],distu[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//distv[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
distv[i]=dist[4][i];
for (pll ii:dag[i]) {
distv[i]=min(distv[i],distv[ii.fi]);
}
for (pll ii:g[i]) {
distv[i]=min(distv[i],distv[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//antidistu[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
antidistu[i]=dist[3][i];
for (pll ii:dag[i]) {
antidistu[i]=min(antidistu[i],antidistu[ii.fi]);
}
for (pll ii:g[i]) {
antidistu[i]=min(antidistu[i],antidistu[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//antidistv[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
antidistv[i]=dist[4][i];
for (pll ii:antidag[i]) {
antidistv[i]=min(antidistv[i],antidistv[ii.fi]);
}
for (pll ii:g[i]) {
antidistv[i]=min(antidistv[i],antidistv[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//distu[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
distu[i]=dist[3][i];
for (pll ii:antidag[i]) {
distu[i]=min(distu[i],distu[ii.fi]);
}
for (pll ii:g[i]) {
distu[i]=min(distu[i],distu[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//distv[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
distv[i]=dist[4][i];
for (pll ii:dag[i]) {
distv[i]=min(distv[i],distv[ii.fi]);
}
for (pll ii:g[i]) {
distv[i]=min(distv[i],distv[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//antidistu[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
antidistu[i]=dist[3][i];
for (pll ii:dag[i]) {
antidistu[i]=min(antidistu[i],antidistu[ii.fi]);
}
for (pll ii:g[i]) {
antidistu[i]=min(antidistu[i],antidistu[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//antidistv[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
antidistv[i]=dist[4][i];
for (pll ii:antidag[i]) {
antidistv[i]=min(antidistv[i],antidistv[ii.fi]);
}
for (pll ii:g[i]) {
antidistv[i]=min(antidistv[i],antidistv[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//distu[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
distu[i]=dist[3][i];
for (pll ii:antidag[i]) {
distu[i]=min(distu[i],distu[ii.fi]);
}
for (pll ii:g[i]) {
distu[i]=min(distu[i],distu[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//distv[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
distv[i]=dist[4][i];
for (pll ii:dag[i]) {
distv[i]=min(distv[i],distv[ii.fi]);
}
for (pll ii:g[i]) {
distv[i]=min(distv[i],distv[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//antidistu[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
antidistu[i]=dist[3][i];
for (pll ii:dag[i]) {
antidistu[i]=min(antidistu[i],antidistu[ii.fi]);
}
for (pll ii:g[i]) {
antidistu[i]=min(antidistu[i],antidistu[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//antidistv[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
antidistv[i]=dist[4][i];
for (pll ii:antidag[i]) {
antidistv[i]=min(antidistv[i],antidistv[ii.fi]);
}
for (pll ii:g[i]) {
antidistv[i]=min(antidistv[i],antidistv[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//distu[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
distu[i]=dist[3][i];
for (pll ii:antidag[i]) {
distu[i]=min(distu[i],distu[ii.fi]);
}
for (pll ii:g[i]) {
distu[i]=min(distu[i],distu[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//distv[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
distv[i]=dist[4][i];
for (pll ii:dag[i]) {
distv[i]=min(distv[i],distv[ii.fi]);
}
for (pll ii:g[i]) {
distv[i]=min(distv[i],distv[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//antidistu[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
antidistu[i]=dist[3][i];
for (pll ii:dag[i]) {
antidistu[i]=min(antidistu[i],antidistu[ii.fi]);
}
for (pll ii:g[i]) {
antidistu[i]=min(antidistu[i],antidistu[ii.fi]+ii.se);
}
}
for (i=1;i<=n;i++) {
//antidistv[i]=oo;
if (dist[1][i]+dist[2][i]!=dist[1][t1]) continue;
antidistv[i]=dist[4][i];
for (pll ii:antidag[i]) {
antidistv[i]=min(antidistv[i],antidistv[ii.fi]);
}
for (pll ii:g[i]) {
antidistv[i]=min(antidistv[i],antidistv[ii.fi]+ii.se);
}
}
res=dist[3][t2];
/*
for (i=1;i<=n;i++) {
cout<<distu[i]<<' ';
}
cout<<'\n';
for (i=1;i<=n;i++) {
cout<<distv[i]<<' ';
}
cout<<'\n';
for (i=1;i<=n;i++) {
cout<<antidistu[i]<<' ';
}
cout<<'\n';
for (i=1;i<=n;i++) {
cout<<antidistv[i]<<' ';
}
cout<<'\n';
*/
for (i=1;i<=n;i++) {
res=min(res,dist[4][i]+min(distu[i],antidistu[i]));
//cout<<"!"<<i<<' '<<res<<' '<<dist[4][i]<<' '<<distu[i]<<' '<<antidistu[i]<<' '<<dist[4][i]+min(distu[i],antidistu[i])<<'\n';
res=min(res,dist[3][i]+min(distv[i],antidistv[i]));
//cout<<"!"<<i<<' '<<res<<' '<<dist[3][i]<<' '<<distv[i]<<' '<<antidistv[i]<<' '<<dist[3][i]+min(distv[i],antidistv[i])<<'\n';
}
for (i=1;i<=n;i++) {
res=min(res,min(distv[i],antidistv[i])+min(distu[i],antidistu[i]));
//cout<<"!"<<i<<' '<<res<<' '<<dist[4][i]<<' '<<distu[i]<<' '<<antidistu[i]<<' '<<dist[4][i]+min(distu[i],antidistu[i])<<'\n';
res=min(res,min(distu[i],antidistu[i])+min(distv[i],antidistv[i]));
//cout<<"!"<<i<<' '<<res<<' '<<dist[3][i]<<' '<<distv[i]<<' '<<antidistv[i]<<' '<<dist[3][i]+min(distv[i],antidistv[i])<<'\n';
}
cout<<res<<'\n';
}
