#include "cyberland.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
const ll MAX = 1e15;
int _H;
vector<int> zeroes;
vector<vector<pair<int, ll> > > connect;
vector<bool> explored;
void explore(int i, vector<int> &a) {
explored[i] = true;
if (a[i] == 0) { zeroes.pb(i); }
if (i == _H) { return; }
for (pair<int, ll> jp : connect[i]) {
int j = jp.f;
if (!explored[j]) { explore(j, a); }
}
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
zeroes.clear();
connect.clear();
explored.clear();
// set-up
_H = H;
connect.resize(N);
explored.resize(N, false);
for (int i = 0; i < M; i++) {
connect[x[i]].pb(mp(y[i], c[i]));
connect[y[i]].pb(mp(x[i], c[i]));
}
// find the cities that are connected (and in-play)
explore(0, arr);
if (!explored[H]) { return -1; }
// run djikstra's from H as the source
// the answer is the minimum among all the 'zeroes'
priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
vector<ll> dists(N, MAX); // distance of a city to H
dists[H] = 0;
pq.push(mp(0, H));
while(!pq.empty()) {
pair<ll, int> p = pq.top(); pq.pop();
ll d = p.f; int i = p.s;
if (dists[i] < d) { continue; }
for (pair<int, ll> jp : connect[i]) {
if (dists[jp.f] > d + jp.s) {
dists[jp.f] = d + jp.s;
pq.push(mp(d + jp.s, jp.f));
}
}
}
ll ans = dists[0];
for (int i : zeroes) { ans = min(ans, dists[i]); }
return ans;
}
