#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 = 100;
vector<pii> T[N];
bool can[N];
bool vv[N];
int A[N];
int ban;
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] && x.fi != ban){
dfs(x.fi);
}
}
}
double d[K][N];
double bins[K];
bool vis[K][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, 90);
bins[0] = 1.0;
for(int i = 1; i <= k ; i ++ ){
bins[i]=bins[i-1]*0.5;
}
ban = h;
for(int i = 0 ; i < n; i ++ ){
T[i].clear();
can[i] = vv[i] = false;
A[i] = arr[i];
}
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 dis;
double nw;
double op = 1e18;
bool fix = false;
for(int j = 0 ; j <= k ; j ++ ){
for(int i = 0 ; i < n; i ++ ){
d[j][i] = 1e18;
vis[j][i] = false;
}
priority_queue<pdi, vector<pdi>, greater<pdi>> pq;
if(j == 0){
d[j][h] = 0.0;
pq.push(mp(0.0, h));
}
else{
for(int i = 0 ; i < n; i ++ ){
if(vis[j - 1][i] && A[i] == 2){
for(auto x : T[i]){
if(x.fi == h) continue;
nw = x.se * bins[j];
if(d[j][x.fi] > d[j - 1][i] + nw){
d[j][x.fi] = d[j - 1][i] + nw;
pq.push(mp(d[j][x.fi], x.fi));
}
}
}
}
}
while(!pq.empty()){
int node = pq.top().se;
dis = pq.top().fi;
pq.pop();
if(vis[j][node]) continue;
vis[j][node] = true;
if(can[node]){
op = min(op, dis);
fix = true;
}
for(auto x : T[node]){
if(x.fi == h) continue;
nw = x.se * bins[j];
if(dis + nw < d[j][x.fi]){
d[j][x.fi] = dis + nw;
pq.push(mp(d[j][x.fi], x.fi));
}
}
}
}
if(fix)
return op;
return -1;
}
