#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using ld = long double;
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
vector<vector<pair<ll,ll>>> adj(N+1);
for(int i = 0; i < M; i++){
ll a = x[i];
ll b = y[i];
ll w = c[i];
adj[a].push_back({b,w});
adj[b].push_back({a,w});
}
// first BFS: check which 0s we can actually reach
vector<bool> vis(N+1,0);
vis[0] = 1;
queue<ll> q;
q.push(0);
while(!q.empty()){
ll at = q.front();
q.pop();
for(pair<ll,ll> p : adj[at]){
ll node = p.first;
if(vis[node]) continue;
if(node == H) continue;
vis[node] = 1;
q.push(node);
}
}
assert(!vis[H]);
// now djk from A
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
vector<ll> dist(N+1, INT_MAX);
pq.push({H,0});
dist[H] = 0;
while(!pq.empty()){
ll node = pq.top().first;
pq.pop();
for(pair<ll,ll> Z : adj[node]){
ll weight = Z.second;
ll place = Z.first;
if(weight+dist[node] < dist[place]){
dist[place] = weight+dist[node];
pq.push({place,dist[place]});
}
}
}
ll mn = 0;
// for(int i = 0;i < N; i++){
// cerr << dist[i] << " ";
// } cerr << endl;
for(int i = 0; i < N; i++){
if(i == H) continue; //cyberland itself
if(!vis[i]) continue; // not visited
if(arr[i] != 0 and i != 0) continue; // not a start point
if(!mn) mn = dist[i];
else mn = min(mn, dist[i]);
}
return mn;
// return -1;
}
