#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>ad[100005];
vector<int>rs,ar,vs(100005);
int h;
void dfs(int u){
if(u==h)return;
if(ar[u]==0)rs.push_back(u);
vs[u]=1;
for(auto v:ad[u])
if(!vs[v.first])
dfs(v.first);
}
double solve(int N,int M,int K,int H,vector<int>x,vector<int>y,vector<int>c,vector<int>arr) {
int wha=70;
h=H;
for(int i=0;i<N;i++)ad[i].clear(),vs[i]=0;
for(int i=0;i<M;i++)
ad[x[i]].push_back({y[i],c[i]}),
ad[y[i]].push_back({x[i],c[i]});
rs.clear();
ar.clear();
rs.push_back(0);
for(auto i:arr)ar.push_back(i);
dfs(0);
priority_queue<pair<double,pair<int,int>>>dj;
for(auto i:rs)dj.push({0,{i,0}});
double R[N][min(K,wha)+1];
for(int i=0;i<N;i++)
for(int j=0;j<=min(K,wha);j++)R[i][j]=1;
for(int i=0;i<=min(K,wha);i++){
priority_queue<pair<double,pair<int,int>>>djn;
while(!dj.empty()){
auto t=dj.top();
dj.pop();
if(R[t.second.first][t.second.second]!=1)continue;
R[t.second.first][t.second.second]=t.first;
if(t.second.first==H)continue;
if(arr[t.second.first]==2&&t.second.second<min(K,wha))
for(auto j:ad[t.second.first])djn.push({t.first/2-j.second,{j.first,t.second.second+1}});
for(auto j:ad[t.second.first])dj.push({t.first-j.second,{j.first,t.second.second}});
}
swap(dj,djn);
}
double res=R[H][0];
for(int i=1;i<=min(K,wha);i++)if(R[H][i]!=1)res=max(res,R[H][i]);
return -res;
}
