#include using namespace std; typedef int ll; typedef long double ld; typedef pair ii; typedef vector vi; typedef vector vvi; typedef vector vii; typedef vector vvii; #define x first #define y second #define pb push_back #define eb emplace_back #define all(v) (v).begin(), (v).end() vvi adj; vvi adj2; vvi d; void getReachable(ll i, ll c, vector& reachable) { if (reachable[i]) return; reachable[i] = true; for (ll j : adj[i]) { if (j == c) continue; getReachable(j, -1, reachable); } } ll dfs(ll i, vi& dfsState, vi& R) { if (dfsState[i] == 2) return R[i]; else if (dfsState[i] == 1) return -1; dfsState[i] = 1; for (ll j : adj2[i]) { ll r = dfs(j, dfsState, R); if (r < 0) return -1; else R[i] = max(R[i], r + d[i][j]); } dfsState[i] = 2; return R[i]; } void run() { ll n, m, c, r; cin >> n >> m >> c >> r; c--; r--; adj = vvi(n); d = vvi(n, vi(n, 1ll<<61)); for (ll i = 0; i < n; i++) { d[i][i] = 0; } // Read input for (ll i = 0; i < m; i++) { ll a, b, l; cin >> a >> b >> l; a--; b--; d[a][b] = l; d[b][a] = l; adj[a].pb(b); adj[b].pb(a); } // APSP for (ll i = 0; i < n; i++) { for (ll j = 0; j < n; j++) { for (ll k = 0; k < n; k++) { d[j][k] = min(d[j][k], d[j][i]+d[i][k]); } } } // Compute new graph adj2 = vvi(n); for (ll i = 0; i < n; i++) { if (adj[i].size() <= 1) continue; ll maxDist = 0; for (ll j = 0; j < n; j++) { if (d[i][j] == maxDist) { adj2[i].pb(j); } else if (d[i][j] > maxDist) { adj2[i] = vi{j}; maxDist = d[i][j]; } } } // Perform first approach ll approachDirection = -1; for (ll i : adj[r]) { if (d[c][r] == d[c][i] + d[i][r]) { approachDirection = i; } } vector reachable(n, false); getReachable(r, approachDirection, reachable); vi posDest; ll maxDist = 0; for (ll i = 0; i < n; i++) { if (reachable[i] && d[r][i] == maxDist) { posDest.pb(i); } else if (reachable[i] && d[r][i] > maxDist) { posDest = vi{i}; maxDist = d[r][i]; } } // Check for reachable cycles in new graph vi dfsState(n, 0), R(n, 0); ll res = d[c][r]; bool pos = true; for (ll i : posDest) { ll partRes = dfs(i, dfsState, R); if (partRes < 0) { pos = false; } else { res = max(res, partRes + d[c][r] + d[r][i]); } } if (pos) { cout << res << endl; } else { cout << "impossible" << endl; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); run(); return 0; }