#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned int ui; const ll mod = 1000000007; typedef long double ld; const ld INF = (ld)10000000000000; typedef pair P; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef complex Point; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair LDP; typedef pair LP; int n, m, l; int t[2000]; struct edge { int to; int cost; }; vector G[2000]; ll d[2000]; priority_queue, greater> q; void dijkstra(int root) { fill(d, d + n, INF); d[root] = 0; q.push({ 0,root }); while (!q.empty()) { LP p = q.top(); q.pop(); int id = p.second; rep(j, G[id].size()) { int to = G[id][j].to; ll nd = p.first + G[id][j].cost; if (nd < d[to]) { d[to] = nd; q.push({ d[to],to }); } } } } ll d2[2000]; int main() { cin >> n >> m >> l; l--; rep(i, n)cin >> t[i]; rep(i, m) { int a, b, c; cin >> a >> b >> c; a--; b--; G[a].push_back({ b, c }); G[b].push_back({ a,c }); } dijkstra(l); rep(i, n) { d2[i] = d[i]; } ll ans = INF; rep(i, n) { dijkstra(i); ll sum = 0; rep(j, n) { sum += 2*d[j] * t[j]; } rep(j, n) { if (t[j] > 0) { ans = min(ans, sum+d2[j] - d[j]); } else { ans = min(ans, sum+d2[j] + d[j]); } } } cout << ans << endl; //stop return 0; }