#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
#include <cstring>
#include <stdio.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef pair<ll,ll> pll;
#define double long double
#define F first
#define S second
const double eps = 1e-9;
#define FOR(i,a,b) for(long long i=a;i<b;i++)
#define all(v) v.begin(),v.end()
// Define MAXN here, globally accessible
const ll MAXN = 1e17; // A sufficiently large value for infinity
template <typename I>
void print(vector<I> &v){
FOR(i,0,v.size()){cout << v[i] << " ";}
cout << "\n";
}
ll gcd(ll a,ll b){
if(a==0){return b;}
else if(b==0){return a;}
else if(a<b){return gcd(b%a,a);}
else{return gcd(a%b,b);}
}
ll lcm(ll a,ll b){
return (a/gcd(a,b))*b;
}
// Global variable or passed by reference to avoid recreating
// Used to store edges on *any* shortest path from s to t
vector<vector<pll>> special_edges_adj;
vector<vector<pll>> special_edges_rev_adj; // For the "adj2" equivalent
// Visited array for DFS to prevent cycles in the shortest path reconstruction
vector<bool> dfs_visited;
vll dist_s_global; // Store dist from s globally or pass around
// build_shortest_path_edges function (removed as it was causing confusion with prev logic,
// and the BFS queue approach directly builds special_edges_adj)
/*
void build_shortest_path_edges(ll current_node, ll target_s_end, const vector<vector<pll>>& adj_original) {
// ... (This function's logic was superseded by the BFS queue in solve)
}
*/
ll func(vector<vector<pll>> &adj_original, vector<vector<pll>> &additional_adj, ll n, ll u_query, ll v_query){
vll dist(n,MAXN); // MAXN is now in scope
vector<bool> visited(n,false);
priority_queue<pll,vector<pll>,greater<pll>> pq;
pq.push({0,u_query});
dist[u_query] = 0;
while(!pq.empty()){
pll c = pq.top();
pq.pop();
ll current_d = c.F;
ll current_u = c.S;
if(visited[current_u]) continue;
visited[current_u] = true;
for(pll &p : adj_original[current_u]){
ll alt = current_d + p.S;
if(alt < dist[p.F]){
dist[p.F] = alt;
pq.push({alt,p.F});
}
}
for(pll &p : additional_adj[current_u]){
ll alt = current_d + p.S;
if(alt < dist[p.F]){
dist[p.F] = alt;
pq.push({alt,p.F});
}
}
}
return dist[v_query];
}
void solve(){
ll n,m;
cin >> n >> m;
n++;
ll s_start, t_end;
cin >> s_start >> t_end;
ll u_query, v_query;
cin >> u_query >> v_query;
vector<vector<pll>> adj_original(n);
for(ll i=0; i<m; ++i){
ll a,b,c;
cin >> a >> b >> c;
adj_original[a].push_back({b,c});
adj_original[b].push_back({a,c});
}
dist_s_global.assign(n, MAXN); // MAXN is now in scope
vector<bool> visited_dijkstra(n, false);
priority_queue<pll,vector<pll>,greater<pll>> pq_s;
pq_s.push({0,s_start});
dist_s_global[s_start] = 0;
while(!pq_s.empty()){
pll c = pq_s.top();
pq_s.pop();
ll current_d = c.F;
ll current_u = c.S;
if(visited_dijkstra[current_u]) continue;
visited_dijkstra[current_u] = true;
for(pll &p : adj_original[current_u]){
ll alt = current_d + p.S;
if(alt < dist_s_global[p.F]){
dist_s_global[p.F] = alt;
pq_s.push({alt,p.F});
}
}
}
special_edges_adj.assign(n, vector<pll>());
special_edges_rev_adj.assign(n, vector<pll>());
// dfs_visited.assign(n, false); // No longer needed for DFS if using BFS queue for special edges
queue<ll> q_sp;
q_sp.push(t_end);
vector<bool> sp_visited_q(n, false);
sp_visited_q[t_end] = true;
while(!q_sp.empty()){
ll current = q_sp.front();
q_sp.pop();
for(const pll& edge : adj_original[current]){
ll neighbor = edge.F;
ll weight = edge.S;
// This condition correctly identifies if 'neighbor' is a predecessor of 'current'
// on a shortest path from 's_start'
if (dist_s_global[neighbor] != MAXN && dist_s_global[current] != MAXN &&
dist_s_global[neighbor] + weight == dist_s_global[current]) {
special_edges_adj[current].push_back({neighbor, 0});
special_edges_rev_adj[neighbor].push_back({current, 0});
if (!sp_visited_q[neighbor]) {
sp_visited_q[neighbor] = true;
q_sp.push(neighbor);
}
}
}
}
cout << min(func(adj_original, special_edges_adj, n, u_query, v_query),
func(adj_original, special_edges_rev_adj, n, u_query, v_query)) << "\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t=1;
while(t--){
solve();
}
return 0;
}
