#include <bits/stdc++.h>
using namespace std;
const double INF = 5e18;
const int mxN = 2e5+100;
const int mxK = 32;
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
double dp[mxN][mxK];
set<pair<int,double>> adj[mxN];
bool on_road[mxN],vis[mxN],clean[mxN];
pair<int,double> tp;
vector<int> ar;
int st=0,last;
bool dfs(int u){
if(on_road[u]) return 1;
vis[u]=1;
for(auto it:adj[u]){
if(!vis[it.fi]&&dfs(it.fi)){
return on_road[u]=1;
}
}
}
void fnd_fz(int u=0,int par=-1,double d=0){
if(clean[u]) st=u,tp.fi=par,tp.se=d;
for(auto it:adj[u]){
if(it.fi^par) fnd_fz(it.fi,u,it.se);
}
}
// dp[u][k]=minimum cost to come on node u with exactly k operation of the divide 2 type
void solve(int u,int par,int K){
for(auto it:adj[u]){
if(it.fi^par){
for(int i=0;i<=K;++i) dp[it.fi][i]=dp[u][i]+it.se;
if(ar[it.fi]==2&&it.fi!=last){
for(int k=1;k<=K;++k){
for(int prev=0;prev<k;++prev){
double curr=dp[u][prev];
if(k==1) dp[it.fi][k]=min(dp[it.fi][k],curr+it.se);
for(int i=0;i<k-prev-1;++i){
curr+=it.se*(i==0?1:2);
curr/=2;
dp[it.fi][k]=min(dp[it.fi][k],curr);
}
}
}
}
solve(it.fi,u,K);
}
}
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
ar=arr,tp.fi=-1,st=0,last=H;
for(int i=0;i<N;++i) adj[i].clear(),on_road[i]=clean[i]=vis[i]=0;
for(int i=0;i<M;++i){
adj[x[i]].insert({y[i],c[i]});
adj[y[i]].insert({x[i],c[i]});
//cout<<x[i]<<" "<<y[i]<<" "<<c[i]<<endl;
}
on_road[H]=1;
dfs(0);
vector<pair<int,double>> rem;
// remove the extra nodes from the end
for(auto it:adj[H]){
if(!on_road[it.fi]) rem.pb(it);
// cout<<it.fi<<endl;
}
for(auto it:rem){
adj[H].erase(it);
}
// remove the extra nodes from the start
rem.clear();
for(auto it:adj[0]){
if(!on_road[it.fi]) rem.pb(it);
}
for(auto it:rem) {
adj[0].erase(it);
// cout<<it.fi<<endl;
}
for(int i=0;i<N;++i){
if(arr[i]==0) clean[i]=1;
}
fnd_fz();
if(tp.fi!=-1){
adj[st].erase(tp);
}
//for(auto it:adj[st]) cout<<it.fi<<endl;
//cout<<st<<endl;
for(int i=0;i<N;++i){
if(i==st) for(int j=0;j<=K;++j) dp[i][j]=0;
else for(int j=0;j<=K;++j) dp[i][j]=INF;
}
solve(st,-1,K);
double ans=INF;
for(int i=0;i<=K;++i) ans=min(ans,dp[H][i]);
return ans;
}
