// JOI_2018.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct Edge {
int a, b;
ll c;
};
vector<ll> dijkstras(int s, vector<vector<pair<int, ll>>>& adj) {
int n = adj.size()-1;
vector<ll> dist(n + 1, INF);
dist[s] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> stuff;
stuff.push({ 0, s });
while (!stuff.empty()) {
auto thing = stuff.top(); stuff.pop();
if (dist[thing.second] < thing.first) continue;
for (auto next : adj[thing.second]) {
if (dist[thing.second] + next.second < dist[next.first]) {
dist[next.first] = dist[thing.second] + next.second;
stuff.push({ dist[next.first], next.first });
}
}
}
return dist;
}
int main()
{
int n, m, s, t, u, v;
cin >> n >> m>>s>>t>>u>>v;
vector<vector<pair<int, ll>>> adj(n + 1);
vector<Edge> edges;
for (int i = 0; i < m; i++) {
int a, b; ll c;
cin >> a >> b >> c;
adj[a].push_back({ b, c });
adj[b].push_back({ a, c });
edges.push_back({ a, b, c });
}
vector<ll> distS = dijkstras(s, adj), distT = dijkstras(t, adj), distU = dijkstras(u, adj), distV = dijkstras(v, adj);
vector<vector<int>> newadj(n + 1);
vector<int> indeg(n + 1, 0);
vector<bool> included(n + 1, false);
for (auto edge : edges) {
int a = edge.a, b = edge.b;
ll c = edge.c;
if (distS[a] + c + distT[b] == distS[t]) {
newadj[a].push_back(b);
indeg[b]++;
included[a] = included[b] = true;
continue;
}
if (distS[b] + c + distT[a] == distS[t]) {
newadj[b].push_back(a);
indeg[a]++;
included[a] = included[b] = true;
continue;
}
}
vector<int> topsort;
queue<int> stuff;
for (int i = 1; i <= n; i++) {
if (included[i] && indeg[i] == 0) {
stuff.push(i);
}
}
while (!stuff.empty()) {
int f = stuff.front(); stuff.pop();
topsort.push_back(f);
for (int i : newadj[f]) {
if (--indeg[i] == 0) {
stuff.push(i);
}
}
}
reverse(topsort.begin(), topsort.end());
vector<ll> bestU(n + 1, INF);
for (int i : topsort) {
bestU[i] = distV[i];
for (int j : newadj[i]) {
bestU[i] = min(bestU[i], bestU[j]);
}
}
ll ans = distU[v];
for (int i : topsort) {
ans = min(bestU[i] + distU[i], ans);
}
cout << ans << "\n";
}
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started:
// 1. Use the Solution Explorer window to add/manage files
// 2. Use the Team Explorer window to connect to source control
// 3. Use the Output window to see build output and other messages
// 4. Use the Error List window to view errors
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file
