#include <iostream> #include <vector> #include <string> #include <cmath> #include <algorithm> #include <utility> #include <queue> #include <set> #include <map> #include <deque> #include <iomanip> #include <cstdio> #include <stack> #include <numeric> using namespace std; typedef long long ll; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<VI> VVI; #define MP make_pair #define PB push_back #define inf 1e+16 #define rep(i,n) for(int i=0;i<(int)(n);++i) vector<vector<pair<ll,int> > > g; int main(){ int n,m,s; cin >> n >> m >> s; vector<ll> dd(n,inf); vector<ll> 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<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >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<n;i++){ pq.push(MP(0,i)); vector<ll> 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; }