#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef int ll; typedef pair PII; typedef vector VI; typedef vector VVI; #define MP make_pair #define PB push_back #define inf 1e+9 #define rep(i,n) for(int i=0;i<(int)(n);++i) vector > > g; int main(){ int n,m,s; cin >> n >> m >> s; vector dd(n,inf); vector t(n); int cnt=0; rep(i,n){ cin >> t[i]; if(t[i]>0)cnt++; } if(cnt==1){ cout << 0 << endl; return 0; } s--; g.resize(n); rep(i,m){ int a,b,c; cin >> a >> b >> c; a--;b--; g[a].push_back(MP(c,b)); g[b].push_back(MP(c,a)); } dd[s] = 0; priority_queue,vector >,greater > >pq; pq.push(MP(0,s)); while(!pq.empty()){ auto x = pq.top(); pq.pop(); if(dd[x.second]!=x.first)continue; for(auto y:g[x.second]){ if(dd[y.second]>dd[x.second]+y.first){ dd[y.second] = dd[x.second]+y.first; pq.push(MP(dd[y.second],y.second)); } } } ll ans = inf; for(int i=0;i d(n,inf); d[i] = 0; while(!pq.empty()){ auto x = pq.top(); pq.pop(); if(d[x.second]!=x.first)continue; for(auto y:g[x.second]){ if(d[y.second]>d[x.second]+y.first){ d[y.second] = d[x.second]+y.first; pq.push(MP(d[y.second],y.second)); } } } ll tmp = 0; rep(j,n){ tmp += 2*d[j]*t[j]; } ll ma = -inf; rep(j,n){ if(t[j]>0){ ma = max(ma,d[j]-dd[j]); } } tmp -= ma; //cerr << tmp << endl; ans = min(ans,tmp); } cout << ans << endl; return 0; }