#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <map>
#include <numeric>
#include <initializer_list>
#include <string>
#include <variant>
#include <set>
#include <bitset>
#include <climits>
#include <stack>
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = INT_MAX;
const int INV2 = 500000004;
using namespace std;
// segment tree odd length omodel
// 1
// 2
// 3 4 5
// so if left side is odd, then I need to --l / 2 to get the parent
// 2
// 3 4
// 5 6 7 8 9
// input
// 10
// 10 3 9 5 2 10 5 9 2 1
struct SegmentTree {
vector<int> tree;
int n;
SegmentTree(int n) {
this->tree = vector<int>(2 * n, 0);
this->n = n;
}
void update(int index, int val) {
int _index = this->n + index;
this->tree[_index] = (this->tree[_index] + val) % MOD;
while (_index > 1) {
_index /= 2;
this->tree[_index] = (this->tree[_index * 2] + this->tree[_index * 2 + 1]) % MOD;
}
}
// queries range [l, r)
int query(int l, int r) {
int res = 0;
l += this->n;
r += this->n;
while (l < r) {
if (l % 2 == 1) res = (res + this->tree[l++]) % MOD;
if (r % 2 == 1) res = (res + this->tree[--r]) % MOD;
l /= 2;
r /= 2;
}
return res;
}
void print() {
cout << "n: " << n << endl;
cout << "tree: ";
for (auto x : this->tree) cout << x << " ";
cout << endl;
cout << endl;
}
};
struct DSU {
vector<int> parent;
vector<int> num_components;
DSU(int n) {
parent = vector<int>(n + 1, 0);
for (int i = 0; i <= n; ++i) parent[i] = i;
num_components = vector<int>(n + 1, 1);
}
int find(int i) {
if (parent[i] != i) {
parent[i] = this->find(parent[i]);
return parent[i];
}
return parent[i];
}
int query(int i) {
int root = this->find(i);
return num_components[root];
}
void merge(int i, int j) {
int root_i = this->find(i);
int root_j = this->find(j);
int num_component_i = num_components[root_i];
int num_component_j = num_components[root_j];
if (rand() % 2) swap(root_i, root_j);
parent[root_i] = root_j;
num_components[root_j] = num_component_i + num_component_j;
}
};
void solve() {
int n, m; cin >> n >> m;
int s, t; cin >> s >> t;
int u, v; cin >> u >> v;
vector<vector<pair<int, ll>>> adj(n + 1);
for (int i = 0; i < m; ++i) {
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({ b, c });
adj[b].push_back({ a, c });
}
vector<vector<int>> prev(n + 1); // previous nodes for dijkstras
{
vector<ll> dist(n + 1, LLONG_MAX);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> que;
que.push({ 0, s });
dist[s] = 0;
while (!que.empty()) {
auto [weight, node] = que.top();
que.pop();
// cout << "processing " << weight << " " << node << endl;
if (dist[node] < weight) continue;
for (auto [next, next_weight] : adj[node]) {
ll alt = weight + next_weight;
if (alt == dist[next]) {
prev[next].push_back(node);
}
else if (alt < dist[next]) {
prev[next].clear(); prev[next].push_back(node);
dist[next] = alt;
que.push({ dist[next], next });
}
}
}
}
// now recover the subgraph?
vector<vector<pair<int, ll>>> adj_f(adj);
vector<vector<pair<int, ll>>> adj_r(adj);
{
queue<int> que;
vector<bool> visited(n + 1, false);
que.push(t);
visited[t] = true;
while (!que.empty()) {
int node = que.front();
que.pop();
if (node == s) break;
for (int prev_node : prev[node]) {
if (!visited[prev_node]) {
que.push(prev_node);
adj_f[prev_node].push_back({ node, 0 }); // train pass
adj_r[prev_node].push_back({ node, 0 });
adj_r[node].push_back({ prev_node, 0 }); // train pass
}
}
}
}
// now dijkstra again to find actual distance from u to v
vector<ll> dist_f(n + 1, LLONG_MAX);
{
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> que;
que.push({ 0, u });
dist_f[u] = 0;
while (!que.empty()) {
auto [weight, node] = que.top();
que.pop();
if (dist_f[node] < weight) continue;
for (auto [next, next_weight] : adj_f[node]) {
ll alt = weight + next_weight; // negative to simplify pq declaration
if (alt < dist_f[next]) {
dist_f[next] = alt;
que.push({ dist_f[next], next});
}
}
}
}
vector<ll> dist_r(n + 1, LLONG_MAX);
{
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> que;
que.push({ 0, u });
dist_r[u] = 0;
while (!que.empty()) {
auto [weight, node] = que.top();
que.pop();
if (dist_r[node] < weight) continue;
for (auto [next, next_weight] : adj_r[node]) {
ll alt = weight + next_weight; // negative to simplify pq declaration
if (alt < dist_r[next]) {
dist_r[next] = alt;
que.push({ dist_r[next], next });
}
}
}
}
// cout << dist_f[v] << " " << dist_r[v] << endl;
cout << min(dist_f[v], dist_r[v]) << endl;
}
int main() {
// usaco
// freopen("mootube.in", "r", stdin);
// freopen("mootube.out", "w", stdout);
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
solve();
return 0;
}
