#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>
#define ld double
typedef long long ll;
typedef pair<long long, long long> pll;
typedef tuple<ld, long long, long long> iii;
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
vector<bool> reachable(N, 0);
vector<vector<pll>> al(N+1);
for(int i=0;i<M;i++){
al[x[i]].push_back({y[i], c[i]});
al[y[i]].push_back({x[i], c[i]});
}
auto dfs=[&](auto && dfs, int c) -> void{
reachable[c]=1;
if(c == H) return;
for(auto [to, w] : al[c]){
if(reachable[to]) continue;
dfs(dfs, to);
}
};
dfs(dfs, 0);
/*for(int i=0;i<N;i++){
cout<<i<<" "<<reachable[i]<<endl;
}
return -1;*/
vector<vector<ld>> dist(N, vector<ld>(K+1, 1e15));
priority_queue<iii,vector<iii>,greater<iii>> pq;
pq.push({0, H, 0});
dist[H][0]=0;
while(!pq.empty()){
auto [cd, c, t] = pq.top(); pq.pop();
if(dist[c][t] < cd) continue;
for(auto [to, w] : al[c]){
ld t1=cd + (ld)w/(ld)(1<<t);
if(dist[to][t] > t1){
dist[to][t] = t1;
pq.push({t1, to, t1});
}
if(t < K and arr[c] == 2){
ld t2=cd + (ld)w/(ld)(1<<(t+1));
if(dist[to][t+1] > t2){
dist[to][t+1]=t2;
pq.push({t2, to, t2});
}
}
}
}
ld ans=1e15;
for(int i=0;i<N;i++){
if((arr[i] == 0 and reachable[i]) or i == 0){
ans=min(ans, *min_element(dist[i].begin(),dist[i].end()));
}
}
return ans;
}
