#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;
int st=0;
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=0,double d=0){
if(clean[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){
dp[it.fi][0]=dp[u][0]+it.se;
for(int i=1;i<=K;++i){
dp[it.fi][i]=(dp[u][i-1]+it.se)/2;
for(int j=1;j<i;++j){
dp[it.fi][i]+=it.se;
dp[it.fi][i]/=2;
}
}
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){
tp.fi=-1,st=0;
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]});
}
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);
}
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);
for(int i=0;i<N;++i){
if(arr[i]==0) clean[i]=1;
}
if(!clean[0]) fnd_fz();
if(tp.fi!=-1){
adj[st].erase(tp);
}
solve(st,-1,K);
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;
}
return dp[H][K];
}
