#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define endl '\n'
#define ff first
#define ss second
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ar array
const int MOD = 1e9 + 7,INF = 1e18, N = 2e5 + 5;
/*
5 2
1 2 2
2 3 2
3 4 2
4 5 2
*/
int ans = INF;
vector <vector <int>> p;
map <pair<int,int> , int> mp;
vector <vector <pair<int,int>>> g;
int n;
void res(int i, vector <int> a, int s, int u, int v){
if(i == s){
// cout<<"here"<<endl;
for(int j = 0;j < (int)a.size() - 1;j++){
mp[{a[j] , a[j + 1]}] = 1;
mp[{a[j + 1] , a[j]}] = 1;
}
// for(int j = 0;j < (int)a.size();j++){
// cout<<a[j]<<' ';
// }
// cout<<endl;
set <pair<int,int>> st;
st.insert({0 , v});
vector <int> cnt(n + 1, INF);
cnt[v] = 0;
while(!st.empty()){
int x = st.begin() -> ss;
st.erase(st.begin());
// cout<<x<<endl;
for(auto [j, c] : g[x]){
int l = c;
if(mp[{j , x}]){
l = 0;
}
if(cnt[j] > cnt[x] + l){
cnt[j] = cnt[x] + l;
st.insert({cnt[j] , j});
}
}
}
for(int j = 0;j < (int)a.size() - 1;j++){
mp[{a[j] , a[j + 1]}] = 0;
mp[{a[j + 1] , a[j]}] = 0;
}
ans = min(ans, cnt[u]);
return;
}
else{
for(int j : p[i]){
a.pb(j);
res(j, a, s, u, v);
a.pop_back();
}
}
}
void solve(){
int m;
cin >> n >> m;
int s, t, u, v;
cin >> s >> t >> u >> v;
p.resize(n + 1);
g.resize(n + 1);
for(int i = 0;i < m;i++){
int a, b, c;
cin >> a >> b >> c;
g[a].pb({b, c});
g[b].pb({a, c});
}
vector <int> cnt(n + 1, INF), way(n + 1);
cnt[s] = 0;
way[s] = 1;
set <pair<int,int>> st;
st.insert({0 , s});
while(!st.empty()){
int x = st.begin() -> ss;
st.erase(st.begin());
for(auto [i, c] : g[x]){
if(cnt[i] > cnt[x] + c){
cnt[i] = cnt[x] + c;
p[i].clear();
p[i].pb(x);
st.insert({cnt[i] , i});
way[i] = way[x];
}
else if(cnt[i] == cnt[x] + c){
p[i].pb(x);
way[i] += way[x];
}
}
}
// cout<<way[t]<< endl;
// for(int i = 1;i <= n;i++){
// cout<< cnt[i] << ' ';
// }
// cout<<endl;
// for(int i = 1;i <= n;i++){
// cout<<i << ": ";
// for(int j : p[i]){
// cout<<j<<' ';
// }
// cout<<endl;
// }
vector <int> h;
h.pb(t);
if(way[t] > 100){
cout<<"jkdfj"<<endl;
return;
}
res(t , h, s, u , v);
cout<< ans <<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int ti = 1;
while (ti--) {
solve();
}
}
