#include "cyberland.h"
#include <bits/stdc++.h>
bool visit[100010];
int type[100010];
long double dist[69][100010];
int NG,MG,KG,HG;
std::vector<std::pair<int,int>> adj[100010];
void dfs(int curr,int par){
//std::cout << '|' << curr;
if(visit[curr])return;
visit[curr]=true;
if(curr==HG)return;
for(auto [to,w]:adj[curr]){
if(to==par)continue;
//std::cout << ' ' << to;
dfs(to,curr);
}
}
long double pow2[100];
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) {
K=std::min(K,68);
NG=N,MG=M,KG=K,HG=H;
pow2[0]=1;
for(int i=1;i<=K;i++)pow2[i]=pow2[i-1]*2;;
for(int i=0;i<N;i++){
type[i]=arr[i];
for(int j=0;j<=K;j++)dist[j][i]=1e15;
}
dist[0][H]=0;
for(int i=0;i<M;i++){
//std::cout << x[i] << ' ' << y[i] << ' ' << c[i] << '\n';
adj[x[i]].push_back({y[i],c[i]});
adj[y[i]].push_back({x[i],c[i]});
}
dfs(0,0);
std::priority_queue<std::pair<long double,std::pair<int,int>>> pq;
pq.push({-0,{0,H}});
long double res = 1e18;
while(!pq.empty()){
long double currWeight = -pq.top().first;
int currDev = pq.top().second.first;
int currNode = pq.top().second.second;
//std::cout << currNode << ' ' << adj[currNode].size() << '\n';
pq.pop();
if(visit[currNode]&&(currNode==0||arr[currNode]==0))res=std::min(res,currWeight);
if(!visit[currNode])continue;
for(auto [to,w]:adj[currNode]){
if(type[currNode]==2&&currDev<K&&dist[currDev+1][to]>currWeight+(((long double)w)/(pow2[currDev+1]))){
dist[currDev+1][to]=currWeight+(((long double)w)/(pow2[currDev+1]));
pq.push({-dist[currDev+1][to],{currDev+1,to}});
}
//std::cout << to << ' ' << dist[currDev][to] << ' ' << currWeight+(((long double)w)/(1<<currDev)) << '\n';
if(dist[currDev][to]>currWeight+(((long double)w)/((pow2[currDev])))){
dist[currDev][to]=currWeight+(((long double)w)/((pow2[currDev])));
pq.push({-dist[currDev][to],{currDev,to}});
}
}
}
if(res>=1e15)res=-1;
return res;
}
