#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
constexpr double INF=DBL_MAX;
constexpr int N=1e5+5,K=70;
vector<pair<int,int>> g[N];
bool vi[N];
double di[N][K+1];
priority_queue<pair<double,pair<int,int>>> pq; // (-d,i,j)
void find0(int u,int&h){
for(auto&[w,v]:g[u]) if(!vi[v]&&v!=h)
vi[u]=1,find0(v,h);
}
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> v) {
k=min(k,K);
for(int i=0;i<n;++i)
g[i]=vector<pair<int,int>>(),
vi[i]=false;
for(int i=0;i<n;++i) for(int j=0;j<=k;++j) di[i][j]=INF;
for(int i=0;i<m;++i)
g[x[i]].emplace_back(c[i],y[i]),
g[y[i]].emplace_back(c[i],x[i]);
find0(0,h);
pq.emplace(0.0,make_pair(0,0)); di[0][0]=0.0;
for(int i=0;i<n;++i) if(v[i]==2&&vi[i])
pq.emplace(0.0,make_pair(i,0)),di[i][0]=0.0;
while(pq.size()){
auto [d,p]=pq.top(); pq.pop();
int i=p.first,j=p.second; d=-d;
if(i==h) continue;
if(d>di[i][j]) continue;
if(v[i]==0){
for(auto&[w,x]:g[i])
if(di[x][j]>w) pq.emplace(-(di[x][j]=w),make_pair(x,j));
}else if(v[i]==1){
for(auto&[w,x]:g[i])
if(di[x][j]>d+w) pq.emplace(-(di[x][j]=d+w),make_pair(x,j));
}else{ // v[i]==2
for(auto&[w,x]:g[i]){
if(d+w<di[x][j]) pq.emplace(-(di[x][j]=d+w),make_pair(x,j));
double nd=d/2.0;
if(j<k&&nd+w<di[x][j+1]) pq.emplace(-(di[x][j+1]=nd+w),make_pair(x,j+1));
}
}
}
double ans=INF;
for(int j=0;j<=k;++j) ans=min(ans,di[h][j]);
return ans==INF?-1:ans;
}
