#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const long long MAX = 5100000; const long long INF = 1LL << 60; const long long mod = 1000000007LL; //const long long mod = 998244353LL; using namespace std; typedef unsigned long long ull; typedef long long ll; void dijkstra(ll start, vector>>& graph, vector& dist) { dist[start] = 0; priority_queue, vector>, greater>> pq; vector used(dist.size(), false); pq.push(make_pair(0, start)); while (!pq.empty()) { ll d, node; tie(d, node) = pq.top(); pq.pop(); if (used[node]) continue; used[node] = true; for (pair element : graph[node]) { ll new_d, new_node; tie(new_node, new_d) = element; new_d += d; if (new_d < dist[new_node]) { dist[new_node] = new_d; pq.push(make_pair(dist[new_node], new_node)); } } } } int main() { /* cin.tie(nullptr); ios::sync_with_stdio(false); */ ll N, M, L; scanf("%lld %lld %lld", &N, &M, &L); L--; vector t(N); for (ll i = 0; i < N; i++) scanf("%lld", &t[i]); vector>> g(N); for (ll i = 0; i < M; i++) { ll a, b, c; scanf("%lld %lld %lld", &a, &b, &c); a--; b--; g[a].emplace_back(b, c); g[b].emplace_back(a, c); } vector> d(N, vector(N, INF)); for (ll i = 0; i < N; i++) { dijkstra(i, g, d[i]); } ll res = INF; for (ll i = 0; i < N; i++) { ll sum = 0; for (ll j = 0; j < N; j++) { sum += t[j] * d[i][j] * 2; } for (ll j = 0; j < N; j++) { if (t[j] == 0) continue; chmin(res, sum + d[L][j] + d[j][i] - d[i][j] * 2); } } cout << res << endl; return 0; }