#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e5+5,K=50,INF=1e9;
int n,m,k,h;
vector<int> arr,min_nx;
vector<bool> vi;
vector<vector<pair<int,int>>> g;
double di[N][K];
priority_queue<pair<double,pair<int,int>>> pq; // (-d,i,j)
void find0(int u){
if(arr[u]==0)
pq.emplace(0.0,make_pair(u,0)),di[u][0]=0;
vi[u]=1;
for(auto&[w,v]:g[u]) if(!vi[v]&&v!=h)
find0(v);
}
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) {
n=_n,m=_m,k=min(_k,49),h=_h,arr=_arr;
g=vector<vector<pair<int,int>>>(n);
min_nx=vector<int>(n,INF);
vi=vector<bool>(n,0);
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]);
for(int i=0;i<n;++i) if(arr[i]==2) for(auto&[w,j]:g[i])
if(j!=h) min_nx[i]=min(min_nx[i],w);
for(auto&v:di) for(auto&x:v) x=1e9;
pq.emplace(0.0,make_pair(0,0)); di[0][0]=0.0;
find0(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;
for(auto&[w,x]:g[i]){
//cerr<<">> "<<x<<" "<<arr[x]<<'\n';
if(arr[x]==0) continue;
else if(arr[x]==1){
double nd=d+(double)w;
if(nd<di[x][j]) pq.emplace(-(di[x][j]=nd),make_pair(x,j));
}else{ // arr[v]==2
if(d+w<di[x][j]) pq.emplace(-(di[x][j]=d+w),make_pair(x,j));
double nd=d/2;
for(int l=j+1;l<=k;++l){
if(nd+w<di[x][l]) pq.emplace(-(di[x][l]=nd+w),make_pair(x,l));
nd=nd/2+min_nx[x];
}
}
}
}
double ans=1e9;
for(int j=0;j<=k;++j)
ans=min(ans,di[h][j]);
return ans;
}
