#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define pri priority_queue
using namespace std;
const int maxn = 1e5;
const int inf = 1e15;
bool debug = 0;
// Problem B
// Subtask 3: Possibly brute force
// Precompute all optimal paths from S->T, then for each path o(n) dijkstra o(nlogn) > o(n + n^2 logn)
int n, m, s, t, u, v, ans = inf;
int dist[maxn+5], a[maxn+5], b[maxn+5], c[maxn+5];
map<pii, int> edge;
vector<int> adj[maxn+5], pre[maxn+5];
vector<int> path;
pri<pii, vector<pii>, greater<pii>> pq;
int len(int a, int b) {
if (a > b) swap(a, b);
return edge[{a, b}];
}
void upd(int a, int b, int c) {
if (a > b) swap(a, b);
edge[{a, b}] = c;
}
void brute_force(int cur) {
if (cur == s) {
// clean the halls
for (int i=0; i<path.size()-1; i++) {
if (debug) cout << path[i] << " -> ";
upd(path[i], path[i+1], 0);
}
if (debug) cout << endl;
// dijkstra
for (int i=1; i<=n; i++) dist[i] = inf;
dist[u] = 0;
pq.push({0, u});
while (!pq.empty()) {
int now = pq.top().se, dis = pq.top().fi; pq.pop();
if (dist[now] < dis) continue;
for (int nxt: adj[now]) {
if (dis + len(now, nxt) >= dist[nxt]) continue;
dist[nxt] = dis + len(now, nxt);
pq.push({dist[nxt], nxt});
}
}
ans = min(ans, dist[v]);
for (int i=1; i<=m; i++) upd(a[i], b[i], c[i]);
return;
}
for (int p: pre[cur]) {
path.push_back(p);
brute_force(p);
path.pop_back();
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
for (int i=1; i<=m; i++) {
cin >> a[i] >> b[i] >> c[i];
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
upd(a[i], b[i], c[i]);
}
for (int i=1; i<=n; i++) dist[i] = inf;
pq.push({0, s});
dist[s] = 0;
while (!pq.empty()) {
int now = pq.top().se, dis = pq.top().fi; pq.pop();
if (dist[now] < dis) continue;
for (int nxt: adj[now]) {
if (dis + len(now, nxt) > dist[nxt]) continue;
if (dis + len(now, nxt) == dist[nxt]) {
pre[nxt].push_back(now);
continue;
}
dist[nxt] = dis + len(now, nxt);
pre[nxt].clear();
pre[nxt].push_back(now);
pq.push({dist[nxt], nxt});
}
}
brute_force(t);
cout << ans << endl;
return 0;
}
