#include <bits/stdc++.h> using namespace std; #define el "\n" #define pii pair<int, int> #define pll pair<ll, ll> #define fi first #define se second #define mp make_pair #define sqr(x) ((x) * (x)) #define FOR(i, l, r) for (int i = l; i <= (r); i++) #define FOD(i, l, r) for (int i = l; i >= (r); i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define sz(x) ((int)(x).size()) #define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); using db = long double; using ll = long long; using ull = unsigned long long; using vi = vector<int>; using vll = vector<ll>; using vpii = vector<pii>; using vpll = vector<pll>; using vvi = vector<vi>; using vvll = vector<vll>; using vbool = vector<bool>; using vvbool = vector<vbool>; template <typename T> using heap = priority_queue<T>; template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>; template<class T> inline bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); } template<class T> inline bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); } // #define DEBUG #ifdef DEBUG #include "D:\cpp\debug.h" #else #define debug(...) #define debug_arr(...) #endif mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); constexpr int N = 1E5 + 5; constexpr int INF = 1E9 + 7; constexpr ll INFLL = 4E18; constexpr int MOD = 1E9 + 7; // 998244353 constexpr double EPS = 1E-10; using Edge = tuple<int, int, int>; vpii adj[N]; vi dag[N]; int in[N]; ll d_s[N], d_u[N], d_v[N], d[N]; ll dp[N], dp_u[N], dp_v[N]; int n, m, s, t, u, v; void dijkstra(int s, ll d[]) { min_heap<pair<ll, int>> pq; fill(d + 1, d + n + 1, INFLL); pq.emplace(0, s); d[s] = 0; while (!pq.empty()) { auto [dist, u] = pq.top(); pq.pop(); if (dist != d[u]) continue; for (auto &[v, w] : adj[u]) { if (chmin(d[v], d[u] + w)) { pq.emplace(d[v], v); } } } } void solve() { cin >> n >> m >> s >> t >> u >> v; vector<Edge> edges; while (m--) { int a, b, w; cin >> a >> b >> w; adj[a].emplace_back(b, w); adj[b].emplace_back(a, w); edges.emplace_back(a, b, w); } dijkstra(s, d_s); dijkstra(u, d_u); dijkstra(v, d_v); for (auto &[a, b, w] : edges) { if (d_s[a] + w == d_s[b]) { dag[a].push_back(b); in[b]++; } if (d_s[b] + w == d_s[a]) { dag[b].push_back(a); in[a]++; } } vi topo; queue<int> q; q.push(s); while (!q.empty()) { int x = q.front(); q.pop(); topo.push_back(x); for (int y : dag[x]) { if (--in[y] == 0) { q.push(y); } } } fill(all(dp), INFLL); fill(all(dp_u), INFLL); fill(all(dp_v), INFLL); dp_u[s] = d_u[s]; dp_v[s] = d_v[s]; dp[s] = dp_u[s] + dp_v[s]; for (int x : topo) { chmin(dp[x], min(dp_u[x] + d_v[x], dp_v[x] + d_u[x])); for (int y : dag[x]) { chmin(dp[y], dp[x]); chmin(dp_u[y], min(dp_u[x], d_u[y])); chmin(dp_v[y], min(dp_v[x], d_v[y])); } } cout << min(dp[t], d_u[v]) << el; } int main() { fast_io #define LOCAL #ifndef LOCAL #define PROBLEM "" freopen(PROBLEM ".INP", "r", stdin); freopen(PROBLEM ".OUT", "w", stdout); #endif int t = 1; // cin >> t; while (t--) solve(); }