#include #define rep(i,a,b) for(int i=a;i=b;i--) #define fore(i,a) for(auto &i:a) #define all(x) (x).begin(),(x).end() //#pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b> E[2010]; vector D[2010]; //--------------------------------------------------------------------------------------------------- int vis[101010]; template using min_priority_queue = priority_queue, greater>; void dijk(int s, vector &D) { D.resize(N); rep(i, 0, N) D[i] = infl; rep(i, 0, N) vis[i] = 0; min_priority_queue> que; D[s] = 0; que.push({ 0, s }); while (!que.empty()) { auto q = que.top(); que.pop(); ll cst = q.first; int cu = q.second; if (vis[cu]) continue; vis[cu] = 1; fore(p, E[cu]) { ll cst2 = cst + p.second; int to = p.first; if (chmin(D[to], cst2)) que.push({ D[to], to }); } } } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M >> L; L--; rep(i, 0, N) cin >> T[i]; rep(i, 0, M) { int a, b, c; cin >> a >> b >> c; a--; b--; E[a].push_back({ b,c }); E[b].push_back({ a,c }); } rep(i, 0, N) dijk(i, D[i]); ll ans = infl; rep(p, 0, N) { ll base = 0; rep(i, 0, N) base += T[i] * D[p][i] * 2; rep(st, 0, N) if(T[st]) { ll sm = D[L][st] + D[st][p]; ll cand = base - D[p][st] * 2 + sm; chmin(ans, cand); } } if (ans == infl) ans = 0; cout << ans << endl; }