#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using std::cout;
using std::endl;
using std::vector;
using std::pair;
pair<vector<vector<int>>, vector<long long>> orig_min_costs(
int from, const vector<vector<pair<int, int>>>& neighbors
) {
vector<long long> min_cost(neighbors.size(), LLONG_MAX);
vector<vector<int>> origins(neighbors.size());
min_cost[from] = 0;
origins[from] = {};
auto cmp = [&] (const int& a, const int& b) { return min_cost[a] > min_cost[b]; };
std::priority_queue<int, vector<int>, decltype(cmp)> frontier(cmp);
frontier.push(from);
while (!frontier.empty()) {
int curr = frontier.top();
frontier.pop();
long long curr_cost = min_cost[curr];
for (auto [n, nc] : neighbors[curr]) {
if (curr_cost + nc < min_cost[n]) {
origins[n] = {curr};
min_cost[n] = curr_cost + nc;
frontier.push(n);
} else if (curr_cost + nc == min_cost[n]) {
origins[n].push_back(curr);
}
}
}
return {origins, min_cost};
}
class SubwaySys {
private:
typedef pair<long long, long long> MeetCost;
const MeetCost INVALID{LLONG_MAX, LLONG_MAX};
const vector<vector<pair<int, int>>> neighbors;
const int pass_start;
const int pass_end;
vector<long long> start_min;
vector<long long> end_min;
vector<vector<int>> come_from;
vector<MeetCost> prev_mins;
void calc_mins(int at) {
if (prev_mins[at] != INVALID) {
return;
}
prev_mins[at] = {start_min[at], end_min[at]};
for (int cf : come_from[at]) {
calc_mins(cf);
MeetCost path_best = {std::min(start_min[at], prev_mins[cf].first),
std::min(end_min[at], prev_mins[cf].second)};
if (path_best.first + path_best.second < prev_mins[at].first + prev_mins[at].second) {
prev_mins[at] = path_best;
}
}
}
public:
SubwaySys(const vector<vector<pair<int, int>>>& neighbors, int pass_start, int pass_end)
: neighbors(neighbors), pass_start(pass_start), pass_end(pass_end) {
come_from = orig_min_costs(pass_start, neighbors).first;
}
long long min_cost(int start, int end) {
prev_mins = vector<MeetCost>(neighbors.size(), INVALID);
start_min = orig_min_costs(start, neighbors).second;
end_min = orig_min_costs(end, neighbors).second;
calc_mins(pass_end);
return std::min(start_min[end], prev_mins[pass_end].first + prev_mins[pass_end].second);
}
};
// https://oj.uz/problem/view/JOI18_commuter_pass (input ommitted due to length)
int main() {
int station_num;
int railway_num;
std::cin >> station_num >> railway_num;
// i'll make all of these 0-indexed later in the code
int pass_start;
int pass_end;
std::cin >> pass_start >> pass_end;
int start;
int end;
std::cin >> start >> end;
vector<vector<pair<int, int>>> neighbors(station_num);
for (int r = 0; r < railway_num; r++) {
int from;
int to;
int cost;
std::cin >> from >> to >> cost;
neighbors[--from].push_back({--to, cost});
neighbors[to].push_back({from, cost});
}
cout << SubwaySys(neighbors, --pass_start, --pass_end).min_cost(--start, --end) << endl;
}
