#include <bits/stdc++.h>
using namespace std;
class Q
{
public:
int node;
long long cost;
Q(int n, long long c): node(n), cost(c){}
bool operator<(Q q) const
{
return cost>q.cost;
}
};
void dfs(int node, int start, vector<set<int>>&paths, set<int>path, vector<int>par[])
{
path.insert(node);
if(start==node)
{
paths.push_back(path);
}
else
{
for(int i=0; i<par[node].size(); i++)
{
dfs(par[node][i], start, paths, path, par);
}
}
path.erase(node);
}
vector<set<int>>dijkstra_1(int start, int end, vector<pair<int, long long int>>a[], int n)
{
//vector<int>path;
priority_queue<Q>q;
set<int>path;
long long dist[n];
vector<int>par[n];
for(int i=0; i<n; i++)
{
dist[i]=LLONG_MAX;
}
q.push(Q(start, 0));
dist[start]=0;
while(!q.empty())
{
Q w=q.top();
q.pop();
if(dist[w.node]<w.cost)
continue;
dist[w.node]=w.cost;
for(int i=0; i<a[w.node].size(); i++)
{
if(dist[a[w.node][i].first]>w.cost+a[w.node][i].second)
{
dist[a[w.node][i].first]=w.cost+a[w.node][i].second;
q.push({a[w.node][i].first, dist[a[w.node][i].first]});
par[a[w.node][i].first].clear();
par[a[w.node][i].first].push_back(w.node);
}
else if(dist[a[w.node][i].first]==w.cost+a[w.node][i].second)
par[a[w.node][i].first].push_back(w.node);
}
}
vector<set<int>>paths;
dfs(end, start, paths, path, par);
for(int i=0; i<n; i++)
par[i].clear();
/*for(int node=end; node!=start; node=par[node])
{
//path.push_back(node);
path.insert(node);
}
path.insert(start);*/
//path.push_back(start);
//reverse(path.begin(), path.end());
return paths;
}
pair<long long, long long>dijkstra_2(int start, int end, vector<pair<int, long long int>>a[], int n, vector<set<int>>paths)
{
priority_queue<Q>q;
long long dist[n];
for(int i=0; i<n; i++)
{
dist[i]=LLONG_MAX;
}
dist[start]=0;
q.push(Q(start, 0));
long long dist1=LLONG_MAX;
while(!q.empty())
{
Q w=q.top();
q.pop();
if(dist[w.node]<w.cost)
continue;
dist[w.node]=w.cost;
for(int i=0; i<paths.size(); i++)
{
if(paths[i].find(w.node)!=paths[i].end())
{
dist1=min(w.cost, dist1);
}
}
for(int i=0; i<a[w.node].size(); i++)
{
pair<int, long long>next=a[w.node][i];
if(dist[next.first]>next.second+w.cost)
{
dist[next.first]=next.second+w.cost;
q.push(Q(next.first, next.second+w.cost));
}
}
}
long long int dist2=dist[end];
return {dist1, dist2};
}
int main()
{
int n, m, S, T, U, V;
cin>>n>>m>>S>>T>>U>>V;
S--; T--; U--; V--;
vector<pair<int, long long int>>a[n];
for(int i=0; i<m; i++)
{
int aa, bb, cc;
cin>>aa>>bb>>cc;
aa--; bb--;
a[aa].push_back({bb, cc});
a[bb].push_back({aa, cc});
}
vector<set<int>>paths=dijkstra_1(S, T, a, n);
/*cout<<paths.size();
for(int i=0; i<paths.size(); i++)
{
for(auto it=paths[i].begin(); it!=paths[i].end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;
}
cout<<endl;*/
pair<long long, long long> dis1=dijkstra_2(U, V, a, n, paths);
pair<long long, long long> dis2=dijkstra_2(V, U, a, n, paths);
cout<<min(dis1.first+dis2.first, dis1.second);
return 0;
}
