#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
#define fi first
#define se second
#define mp make_pair
const int N = (int)1e5 + 10;
const int K = 65;
vector<pii> T[N];
bool can[N];
bool vv[N];
int A[N];
void dfs(int u){
vv[u]=true;
if(u == 0 || A[u] == 0) can[u] = true;
for(auto x : T[u]){
if(!vv[x.fi]){
dfs(x.fi);
}
}
}
double d[N];
bool vis[N];
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
k = min(k, 60);
for(int i = 0 ; i < n; i ++ ){
T[i].clear();
can[i] = vv[i] = false;
A[i] = arr[i];
d[i] = 1e18;
vis[i] = false;
}
for(int i = 0 ; i < m ; i ++ ){
T[x[i]].push_back(mp(y[i], c[i]));
T[y[i]].push_back(mp(x[i], c[i]));
}
dfs(0);
double sol = 1e18;
priority_queue<pdi, vector<pdi>, greater<pdi>> pq;
d[h] = 0.0;
pq.push(mp(0.0, h));
int node;
double res;
while(!pq.empty()){
node = pq.top().se;
res = pq.top().fi;
pq.pop();
if(vis[node]) continue;
if(can[node]) sol = min(sol, res);
for(auto x : T[node]){
if(d[x.fi] > d[node] + x.se){
d[x.fi] = d[node] + x.se;
pq.push(mp(d[x.fi], x.fi));
}
}
}
return sol;
}
