#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mxN = 1e5+5;
const int mxM = 2e5+5;
struct edge
{
int u, v;
ll c;
int rev;
};
vector<int> out[mxN];
vector<int> in[mxN];
vector<int> new_out[mxN];
vector<int> new_in[mxN];
edge edges[2*mxM];
ll best[mxN];
bool ok[mxN]; ///vertices on shortest path
bool done[mxN];
bool cut[2*mxM];
bool fix(int i, int t)
{
if(i == t) return true;
if(done[i]) return ok[i];
done[i] = true;
for(int e : out[i])
{
int j = edges[e].v;
if(cut[e]) continue;
if(fix(j, t))
{
ok[i]=1;
new_out[i].push_back(e);
new_in[j].push_back(edges[e].rev);
}
}
return ok[i];
}
/// node, used, using, direction
ll dp[mxN][2][2][2];
struct pos
{
int i, used, cur, dir;
bool operator<(const pos& p) const
{
return i < p.i;
}
};
ll solve(int u, int v)
{
for(int i = 0; i < mxN; i++)
for(int j = 0; j < 2; j++)
for(int k = 0; k < 2; k++)
dp[i][j][k][0] = dp[i][j][k][1] = 1e18;
ll ans = 1e18;
dp[u][0][0][0] = 0;
priority_queue<pair<ll, pos>> q;
q.push({0, {u, 0, 0, 0}});
while(!q.empty())
{
auto par = q.top(); q.pop();
pos p = par.second;
int i = p.i;
ll cost = -par.first;
if(cost > dp[p.i][p.used][p.cur][p.dir]) continue;
if(i == v)
{
ans = min(ans, cost);
continue;
}
if(!p.used)
{
if(!p.cur || !p.dir)
{
for(auto e : new_out[i]) ///kreni u 0 dir
{
int j = edges[e].v;
if(cost < dp[j][0][1][0])
{
dp[j][0][1][0] = cost;
q.push({-cost, {j, 0, 1, 0}});
}
}
}
if(!p.cur || p.dir)
{
for(auto e : new_in[i]) ///kreni u 1 dir
{
int j = edges[e].v;
if(cost < dp[j][0][1][1])
{
dp[j][0][1][1] = cost;
q.push({-cost, {j, 0, 1, 1}});
}
}
}
if(p.cur)
{
for(auto e : out[i]) ///canceluj
{
int j = edges[e].v;
if(cost + edges[e].c < dp[j][1][0][0])
{
dp[j][1][0][0] = cost + edges[e].c;
q.push({-dp[j][1][0][0], {j,1,0,0}});
}
}
}
else
{
for(auto e : out[i]) ///klasicno samo nastavi !used
{
int j = edges[e].v;
if(cost + edges[e].c < dp[j][0][0][0])
{
dp[j][0][0][0] = cost + edges[e].c;
q.push({-dp[j][0][0][0], {j,0,0,0}});
}
}
}
}
else
{
for(auto e : out[i]) ///klasicno samo nastavi used
{
int j = edges[e].v;
if(cost + edges[e].c < dp[j][1][0][0])
{
dp[j][1][0][0] = cost + edges[e].c;
q.push({-dp[j][1][0][0], {j,1,0,0}});
}
}
}
}
return ans;
}
int main()
{
for(int i = 0; i < mxN; i++) best[i] = 1e18;
int n, m;
cin >> n >> m;
int s, t, U, V;
cin >> s >> t >> U >> V;
for(int i = 0; i < m; i++)
{
int u, v; ll c; cin >> u >> v >> c;
edges[i*2] = {u,v,c,i*2+1};
edges[i*2+1] = {v,u,c,i*2};
out[u].push_back(i*2);
in[u].push_back(i*2+1);
out[v].push_back(i*2+1);
in[v].push_back(i*2);
}
best[s] = 0;
///cost, to, edge
priority_queue<pair<ll, int>> q;
q.push({0, s});
while(!q.empty())
{
auto cur = q.top(); q.pop();
int i = cur.second;
int cost = -cur.first;
if(cost > best[i]) continue;
for(auto e : in[i])
{
int u = edges[e].u, v = i;
ll c = edges[e].c;
if(best[u] + c > best[v]) cut[e] = true;
}
for(auto e : out[i])
{
int u = i, v = edges[e].v;
ll c = edges[e].c;
if(best[u] + c < best[v])
{
best[v] = best[u] + c;
q.push({-best[v], v});
}
}
}
fix(s, t);
/*for(int i = 1; i <= n; i++)
{
cout << "node " << i << "\n";
for(int e : new_out[i])
{
cout << edges[e].c << " ";
}
cout << "\n";
}
cout << "*********************************\n";
for(int i = 1; i <= n; i++)
{
cout << "node " << i << "\n";
for(int e : new_in[i])
{
cout << edges[e].u << edges[e].v << " ";
}
cout << "\n";
}
cout<<"\n\n";*/
cout << solve(U, V);
}
/*
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
6 5 1
4 4
1 4
0 0
1 2 1
1 3 1
2 4 1
3 4 1
*/
