#include using namespace std; #define int long long #define stoi stoll using ll=long long; using vi=vector; using pii=pair; #define ALL(c) begin(c),end(c) #define RALL(c) rbegin(c),rend(c) #define ITR(i,b,e) for(auto i=(b);i!=(e);++i) #define FORE(x,c) for(auto &&x:c) #define REPF(i,a,n) for(int i=a,i##len=(int)(n);i=0;--i) #define SZ(c) ((int)c.size()) #define CONTAIN(c,x) (c.find(x)!=end(c)) #define INSEG(l,x,r) ((l)<=(x)&&(x)<(r)) #define dump(...) #define pb push_back #define _ 0 const signed INF_=1001001001; const long long INF=1001001001001001001LL; const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0}; template ostream& operator<<(ostream &os,const vector &v) { ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;} template istream& operator>>(istream &is,vector &v) { ITR(i,begin(v),end(v)) is>>*i;return is;} template istream& operator>>(istream &is, pair &p) { is>>p.first>>p.second;return is;} template bool chmax(T &a,const U &b){return a bool chmin(T &a,const U &b){return a>b?a=b,1:0;} template void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));} template using heap=priority_queue,greater>; struct before_main_function { before_main_function() { cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(15) << fixed; #define endl "\n" } } before_main_function; //------------------8<------------------------------------8<-------------------- vector dijkstra(vector> &g, int S) { int N = SZ(g); vector dist(N, INF); dist[S] = 0; heap hp; hp.push({0, S}); while (!hp.empty()) { int v = hp.top().second; hp.pop(); FORE(e, g[v]) { int w = e.first; int c = e.second; if (chmin(dist[w], dist[v] + c)) { hp.push({dist[w], w}); } } } return dist; } signed main() { int N, M, L; cin >> N >> M >> L; L--; vector t(N); cin >> t; vector> g(N); 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}); } auto fromL = dijkstra(g, L); int fir = 0; REP(i, N) if (t[i] > 0) fir = i; REP(i, N) { if (t[i] > 0 && fromL[fir] > fromL[i]) { fir = i; } } t[fir]--; int ans = INF; REP(i, N) { auto dist = dijkstra(g, i); int tmp = fromL[fir] + dist[fir]; REP(j, N) { tmp += dist[j] * 2 * t[j]; } chmin(ans, tmp); } cout << ans << endl; return (0^_^0); }