#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
const long long INF = numeric_limits<long long>::max();
struct Railway {
int start;
int end;
long long fare;
};
struct Node {
int station;
long long cost;
bool operator>(const Node& other) const {
return cost > other.cost;
}
};
long long findMinCost(const vector<vector<Railway>>& graph, int N, int S, int T, int U, int V) {
vector<long long> dist(N + 1, INF);
dist[S] = 0;
priority_queue<Node, vector<Node>, greater<Node>> pq;
pq.push({S, 0});
while (!pq.empty()) {
Node node = pq.top();
pq.pop();
int station = node.station;
long long cost = node.cost;
if (cost > dist[station]) {
continue;
}
for (const Railway& railway : graph[station]) {
int nextStation = railway.end;
long long fare = railway.fare;
if (dist[station] + fare < dist[nextStation]) {
dist[nextStation] = dist[station] + fare;
pq.push({nextStation, dist[nextStation]});
}
}
}
long long minCost = INF;
// Calculate the minimum cost from U to V considering all possible routes between S and T
for (const Railway& railway1 : graph[U]) {
for (const Railway& railway2 : graph[V]) {
if (dist[railway1.start] + railway1.fare + dist[railway2.end] < minCost) {
minCost = dist[railway1.start] + railway1.fare + dist[railway2.end];
}
}
}
return minCost;
}
int main() {
int N, M;
cin >> N >> M;
int S, T;
cin >> S >> T;
int U, V;
cin >> U >> V;
vector<vector<Railway>> graph(N + 1);
for (int i = 1; i <= M; i++) {
int A, B;
long long C;
cin >> A >> B >> C;
graph[A].push_back({A, B, C});
graph[B].push_back({B, A, C});
}
long long minCost = findMinCost(graph, N, S, T, U, V);
cout << minCost << endl;
return 0;
}
