#include using namespace std; using ll = long long; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll n, m, x, y, z, l; cin >> n >> m >> l; l--; vector t(n); for (ll i = 0; i < n; i++) { cin >> t[i]; } vector>> e(n); for (int i=0; i> x >> y >> z; x--; y--; e[x].push_back({y, z}); e[y].push_back({x, z}); } vector dist(n, vector(n, 1e18)); for (int i=0; i, vector>, greater>> que; que.push({0, i}); dist[i][i] = 0; while(!que.empty()){ tie(z, x) = que.top(); que.pop(); if (dist[i][x] < z) continue; for (auto [y, w] : e[x]){ if (dist[i][y] > dist[i][x] + w){ dist[i][y] = dist[i][x] + w; que.push({dist[i][y], y}); } } } } int cnt=0; for (int i=0; i 0) cnt++; } if (cnt == 1){ cout << 0 << endl; return 0; } ll ans = 1e18; for (int i=0; i 0) ans = min(ans, sm+dist[l][j]-dist[i][j]); } } cout << ans << endl; return 0; }