// // // Codeforces: ganariya // AtCoder: ganariya2525 // MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM // MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM // MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM // MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMHBYYYWMMMM#BYYTTTYWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM // MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMB9O1==?????zzCC111>>;;;;;;;;;;;>>>>>;;;;;;;;;:;?TMMMMMMMMMMMMMMMMMMMMMMMMMMMM // MMMMMMMMMMMMMMMMMMMMMMMMMMM9ttlllllllll=l=======?????????>>>>>>;;;;;;;;;;?TMMMMMMMMMMMMMMMMMMMMMMMMM // MMMMMMMMMMMMMMMMMMMMMMMMBOttOtttttltlllllllll=======??????????>>>>>>>;;;;;;?TMMMMMMMMMMMMMMMMMMMMMMM // MMMMMMMMMMMMMMMMMMMMMMBttwOtttttttttttttlllllllll========?????????>>>>>>;;;;;>>>>>;;?HMMMMMMMMMMMMMMMMMMM // MMMMMMMMMMMMMMMMMMMSw0trtrrtrtrttrtttttttttttttlllOllllll========????<>>>>>ZMMMMMMMMMMMMMMMMMM // MMMMMMMMMMMMMMMMMMX0ttrtrOOttrttrttOOttttttttttttltwllllllllll========??wy?????>>>vZMMMMMMMMMMMMMMMM // MMMMMMMMMMMMMMMMM0ttrI+wV1rtttttttwZtttttttltttOwylOXOllllllllllll=l====1dkz???????vZdMMMMMMMMMMMMMM // MMMMMMMMMMMMMMMSrrwrtwZCjttttttttwSttOlllltllllwtXOlZkOlllllllllllllll==z+dk===?????X2JMMMMMMMMMMMMM // MMMMMMMMMMMMMBrtwwtrw0dktDOWOtlttltttOOttltO<;+WOllllllXlllzMMMMMMMMMM // MMMMMMMM9OdM#Ottd$;;;;;?WOw_WWOtttttttttOttI<;;;;;J(I~dkwl(WkttlttlOOwWk<;;:;;zHttttttwOllllMMMMMMMMM // MMMMMMBdMMM8tttdI+zttttttdSXt~dlzXwlllzzOzzzzzlldkW<~?kOk~?sx++++jdHmH6+++<;;jdZtttttdkOtlldMMMMMMMM // MMMMM#dMMM#tttw0+tttttttdKdf((RsdfRllllldZllltlldWK~~_W0w_~OWOlOdgg9ZtOWOtttz+wktttttdpktttwMMMMMMMM // MMMMMWMMMMSlttdIttttttOdWHH>~(IzWDRll=llzRlllzlldk$>++dkd<~_XkdgH9tttttdktttt+OkrttrtdfpkttOMMMMMMMM // MMMMNWMMM#Zttlk=tttttOXWWd$_.(IdW1R=llll=SlllzOldK<_._(kd6+-(MM9lltttttrWktttztWZttrwXppWttrMMMMMMMM // MMMMNMMMM#lltwDzttllOXyW0X:..(OXk~?CdklllltttttXdXttzOWktrwwWpfpkrtMMMMMMMM // MMMMMMMMM@ltldIzlttOXyW$w$```(OyD(Rl==llldZ=llIlw;~```-Xd:~~~~UkylltttAyHdgSrzObRtOXwpfppWrrMMMMMMMM // MMMMMMMMM@llldtlllldVyW+d>```.wZ$ wl==lI=wRl=ll=w<```` dd_..~~(RZXOQdggHH9ZwrzwHWrdXXppfppkrMMMMMMMM // MMMMMMMMM#llldlltlwyyyD(S-...,Wk] zI=l=llzWzl=l=P~```` jZ``...~zQkH@MBUtrZtrtldHRdSdpfpffpkwMMMMMMMM // MMMMNMMMMNZllXtllldVyW3(Mf=.dVT7.dfppffppSXSMMMMMMMM // MMMMMMMMMMMMMRzuHzXyZXH.``````````````` ?zz ``````` ZKvTHHbWt `` XZyyHZWOdSZ<::~`(fpfpfffXp0WMMMMMMM // MMMMMMMMMMMMMKzyyHvyZZW____.`````````````.I_```````` ?nJzX7^````.WXWyyHyWKZ<:::_`Jffpfpfpfp0WMMMMMMM // MMMMMMMMMMMMM@zZyZWwWyXo-_~(~ ```````````` `````````````` _`````.WXkyyVWmWc::<~ .HffppfffffkXMMMMMMM // MMMMMMMMMMMMMKzZZZZXkUXr~....```````....```````````` ... ````..JXWWyyW83vXx~..WfffVfWVffffkdMMMMMMM // MMMMMMMMMMMMMRzZZZZZZZZb````````````<````````````./<~._<_.____`(WfdyW3<:~~(XWkVVVVVVVHVVVVV0dMMMMMMM // MMMMMMMMMMMMMSzZZZZZZZWX-```````````````````````````.......~~._j9jX=_~~_(XZyVHHkyyyyWHyyykykOMMMMMMM // MMMMMMMMMMMMMSzuuuuuZXWZW,```````````````````````````````.``..(3::::;;J=:dZuZuZd#uuruuuud#uuuXMMMNXdMMMMM // MMMMMMMMMMMMMNOvzzXkvMRzzzzXKzuzzzXh, `````````````..JC<;:;;:;;+7<:~(HHuXIdNuuzuuuXMSuuuWMMMMROMMMMM // MMMMMMMMMMMMMNvvvrdkvM#vzzzzHzzzzzuzzUG. ``` ...JdY<:;:;:::;;+v<~~~:(HpHmzMNXZzuzzd#zzzdMMMMMMRdMMMM // MMMMMMMMMMMMMNwrrvdRrMNwvvvvdRvvvzwkzzzzXWWHY=~~O+::::::::<+<~~~~~~~dppppWMMkZzzzwM#zzdMMMMMMMMNMMMM // MMMMMMMMMMMMMM#rrrwRrMMbOrrOZNkrvvvXwvvvvvwX;.~._W_:::::(?!~~~~~~~~(HpppppppHWdvwM#XwdMMMMMMMMMMNMMM // MMMMMMMMMMMMMMNyrrrRrWMMmzOrzdNyrrrZNvrwQWWfb....(r~~_J>_.....~.~~-dpfpffpfpppWHHMNdMMMMMMMMMMMMMMMM // MMMMMMMMMMMMMMMNrtrStdMMMNxzrzMNmrrrdNWfVfffP._-.(~_J!............JpfpffpfpfffpppWNppppHMMMMMMMMMMMM // MMMMMMMMMMMMMMMMNOtXtdMMMMMNxzZMMNmgHyVVVVVW%..?/(.,(x-..........(HfffpffpffpffWHHffpffppfVyyWMMMMMM //include //------------------------------------------ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";} #define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}} using LL = long long; //~~~~~~~~~~~~~~~~~~~~~_(^~^ 」 ∠)_~~~~~~~~~~~~~~~~~~~~~ constexpr int MAX_V = 2020; constexpr LL INF = 1e17; typedef pair PLI; struct edge { LL to; LL cost; }; vector G[MAX_V]; void dijkstra(int s, vector &dist) { dist[s] = 0; priority_queue, greater> Q; Q.push(make_pair(0, s)); while (!Q.empty()) { auto p = Q.top(); Q.pop(); int v = p.second; LL cost = p.first; if (cost > dist[v]) continue; for (int i = 0; i < G[v].size(); i++) { edge &e = G[v][i]; if (dist[e.to] > dist[v] + e.cost) { dist[e.to] = dist[v] + e.cost; Q.push(make_pair(dist[e.to], e.to)); } } } } int main() { int N, M, L; cin >> N >> M >> L, L--; int cnt = 0; vector t(N); for (int i = 0; i < N; i++) cin >> t[i]; for (int i = 0; i < N; i++) if (t[i]) cnt++; if (cnt == 1) { cout << 0 << endl; return 0; } vector a(M), b(M), c(M); for (int i = 0; i < M; i++) { cin >> a[i] >> b[i] >> c[i]; a[i]--, b[i]--; G[a[i]].push_back(edge({b[i], c[i]})); G[b[i]].push_back(edge({a[i], c[i]})); } vector> dist(N, vector(N, INF)); for (int i = 0; i < N; i++) dijkstra(i, dist[i]); LL ans = INF; for (int i = 0; i < N; i++) { LL cost = 0; for (int j = 0; j < N; j++) cost += dist[i][j] * t[j] * 2LL; for (int j = 0; j < N; j++) { LL c = cost; if (t[j]) { c += dist[L][j]; c -= dist[j][i]; ans = min(c, ans); } } } cout << ans << endl; return 0; }