#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int st, vector<array<int,2>>g[], bool vis[], int tar){
vis[st]=1;
if(st==tar)
return;
for(array<int,2>e:g[st]){
if(vis[e[0]])
continue;
dfs(e[0],g,vis,tar);
}
}
const int mxk = 61;
const double inf = 1e18;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<array<int,2>>g[N];
for(int i = 0;i<M;i++){
g[x[i]].push_back({y[i],c[i]});
g[y[i]].push_back({x[i],c[i]});
}
bool vis[N];
fill(vis,vis+N,0);
dfs(0,g,vis,H);
if(!vis[H])
return -1;
double dist[N][mxk];
for(int i = 0;i<N;i++){
fill(dist[i],dist[i]+mxk,inf);
}
priority_queue<tuple<double,int,int>,vector<tuple<double,int,int>>,greater<tuple<double,int,int>>>pq;
//{time,numk,node}
pq.push({0,0,0});
dist[0][0]=0;
for(int i = 0;i<N;i++){
if(arr[i]==0&&vis[i]){
pq.push({0,0,i});
dist[i][0]=0;
}
}
while(!pq.empty()){
auto [time,numk,u] = pq.top();
pq.pop();
if(dist[u][numk]<time){
continue;
}
if(u==H)
continue;
for(array<int,2>e:g[u]){
if(arr[e[0]]==0)
continue;
double nxd = time+e[1];
if(dist[e[0]][numk]>nxd){
dist[e[0]][numk]=nxd;
pq.push({nxd,numk,e[0]});
}
}
}
///curk = 0 done
for(int curk = 1;curk<mxk;curk++){
assert(pq.empty());
for(int i = 0;i<N;i++){
if(arr[i]==2&&vis[i]&&dist[i][curk-1]!=inf){
pq.push({dist[i][curk-1]/2,curk,i});
dist[i][curk]=dist[i][curk-1]/2;
}
}
while(!pq.empty()){
auto [time,numk,u] = pq.top();
pq.pop();
if(dist[u][numk]<time){
continue;
}
if(u==H)
continue;
for(array<int,2>e:g[u]){
if(arr[e[0]]==0)
continue;
double nxd = time+e[1];
if(dist[e[0]][numk]>nxd){
dist[e[0]][numk]=nxd;
pq.push({nxd,numk,e[0]});
}
}
}
}
double ans = inf;
for(int i = 0;i<=min(mxk-1,K);i++){
ans=min(ans,dist[H][i]);
}
return ans;
}
