#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <functional>
#include <cassert>
using namespace std;
//#define debug
#define int long long
int N, M;
int S, T;
int U, V;
#define assert_in(a)assert(a < N);assert(a >= 0);
#define Qnode priority_queue<Node, vector<Node>, greater<Node>>
vector<map<int, int>> G;
class Node{
public:
int cost, node, from;
bool used=false;
const bool operator>(const Node& o) const{
return cost > o.cost;
}
const bool operator>=(const Node& o) const{
return cost >= o.cost;
}
const bool operator<=(const Node& o) const{
return cost <= o.cost;
}
const bool operator<(const Node& o) const{
return cost < o.cost;
}
};
vector<bool> is_solut;
vector<bool> is_in_solut(vector<vector<int>> G, int node){
vector<bool> visited(N, false);
function<void(int)> dfs;
dfs = [&](int node){
if(visited[node])return;
visited[node] = true;
for(int next_node:G[node]){
if(next_node == -1)continue;
if(!visited[next_node])
dfs(next_node);
}
};
dfs(node);
return visited;
}
void add_recurs(Qnode* Q, vector<vector<int>>& G, Node node, vector<bool>& visited){
for(int next_node:G[node.node]){
if(!visited[next_node*2+1] && is_solut[next_node]){
visited[next_node*2+1] = true;
Q->push({node.cost, next_node, node.node, true});
add_recurs(Q, G, node, visited);
visited[next_node*2+1] = false;
}
}
}
const int INF = 1'000'000'000'000'000LL;
vector<int> dp;
vector<vector<int>> S_Tup;
vector<vector<int>> S_Tdown;
int dp_dfs(int node, bool used);
int call_recurs(int node, vector<vector<int>> &_G){
int res = INF;
for(int next_node:_G[node]){
if(is_solut[next_node]){
res = min(res, dp_dfs(node, true));
res = min(res, call_recurs(next_node, _G));
}
}
return res;
}
int deep = 0;
int dp_dfs(int node, bool used){
//cout << node << " " << used << " ";
int res = INF;
int key = node*2+(used>0);
//cout << key << ' ' << dp[key] << '\n';
if(dp[key] != -1){
/*#ifdef debug
for(int i=0; i<deep; i++)cout << ' ';
cout << node << ' ' << used << ':' << dp[key] << '\n';
#endif*/
return dp[key];
}
dp[key] = INF;
/*#ifdef debug
for(int i=0; i<deep; i++)cout << ' ';
cout << node << ' ' << used << ' ' << is_solut[node] << "->\n";
#endif*/
deep++;
for(auto A:G[node])
res = min(res, dp_dfs(A.first, used)+A.second);
if(!used && is_solut[node]){
res = min(
res,
min(
call_recurs(node, S_Tup),
call_recurs(node, S_Tdown)
)
);
}
deep--;
dp[key] = res;
/*#ifdef debug
for(int i=0; i<deep; i++)cout << ' ';
cout << ":" << res << '\n';
#endif*/
return res;
}
signed main(){
cin >> N >> M;
cin >> S >> T;
cin >> U >> V;
S--, U--, T--, V--;
G = vector<map<int, int>>(N);
assert_in(S);assert_in(T);
assert_in(U);assert_in(V);
for(int i=0; i<M; i++){
int node0, node1, cost;
cin >> node0 >> node1 >> cost;
node0--, node1--;
assert_in(node0);assert_in(node1);
G[node0][node1] = cost;
G[node1][node0] = cost;
}
Qnode Q;
vector<int> S_T(N, -1);
S_Tup = vector<vector<int>>(N);
S_Tdown = vector<vector<int>>(N);
Q.push({0, S, -1});
while(!Q.empty()){
Node cur=Q.top();
Q.pop();
assert_in(cur.node);
//cout << cur.node << ' ' << cur.from << ' ' << cur.cost << '\n';
if(S_T[cur.node] != -1){
if(S_T[cur.node] == cur.cost && cur.from != -1){
S_Tup[cur.node].push_back(cur.from);
S_Tdown[cur.from].push_back(cur.node);
}
continue;
}
//if(cur.node == T)break;
S_T[cur.node] = cur.cost;
if(cur.from != -1){
S_Tup[cur.node].push_back(cur.from);
S_Tdown[cur.from].push_back(cur.node);
}
for(auto A:G[cur.node]){
if(S_T[A.first] == -1)
Q.push({cur.cost+A.second, A.first, cur.node});
}
}
is_solut = is_in_solut(S_Tup, T);
/*#ifdef debug
int temp=0;
for(vector<int> A:S_Tup){
cout << temp << " :";
for(int n:A)cout << ' ' << n;
cout << '\n';
temp++;
}
temp = 0;
for(vector<int> A:S_Tdown){
cout << temp << " :";
for(int n:A)cout << ' ' << n;
cout << '\n';
temp++;
}
for(int t:is_solut)cout << t << ' ';
cout << '\n';
#endif*/
dp = vector<int>(N*2, -1);
dp[V*2] = 0;
dp[V*2+1] = 0;
cout << dp_dfs(U, false) << '\n';
}
