#include <algorithm>
#include <queue>
const int Nx=100010;
const double inf=1e24;
int n,m,k,h,ab[Nx];
struct edge{int to,nex,val,typ;};
edge a[300*Nx];
int head[75*Nx],cnt;
void add(int u,int v,int w,int t)
{
a[++cnt]=edge{v,head[u],w,t};
head[u]=cnt;
}
struct node
{
int idx;double val;
bool operator < (const node &x) const
{
if(idx/n!=x.idx/n)
return idx/n>x.idx/n;
return val>x.val;
}
};
int id(int x,int lev){return x+lev*n;}
void find_zpair(int p)
{
ab[p]=1;
int i;
for(i=head[p];i;i=a[i].nex)
{
if(ab[a[i].to]==0&&p!=h)
find_zpair(a[i].to);
}
}
double dis[75*Nx];
int fin[75*Nx];
void clear_all()
{
int i;
for(i=0;i<n;i++)
ab[i]=0;
for(i=0;i<=(k+1)*n+1;i++)
head[i]=dis[i]=fin[i]=0;
cnt=n=m=k=h=0;
}
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)
{
clear_all();
n=N,m=M,k=K,h=H;
int i,j,now,fx,fy;
for(i=0;i<M;i++)
{
add(X[i],Y[i],C[i],1);
add(Y[i],X[i],C[i],1);
}
find_zpair(0);
if(ab[H]==0)
return -1;
for(i=0;i<=N;i++)
head[i]=0;
cnt=0;
for(i=0;i<M;i++)
{
for(j=0;j<=K;j++)
{
if(X[i]!=H)
add(id(X[i],j),id(Y[i],j),C[i],1);
if(Y[i]!=H)
add(id(Y[i],j),id(X[i],j),C[i],1);
if(j!=K&&X[i]!=H&&arr[Y[i]]==2)
add(id(X[i],j),id(Y[i],j+1),C[i],2);
if(j!=K&&Y[i]!=H&&arr[X[i]]==2)
add(id(Y[i],j),id(X[i],j+1),C[i],2);
}
}
for(i=0;i<=(K+1)*N+1;i++)
dis[i]=inf,fin[i]=0;
std::priority_queue<node> hea;
for(i=0;i<N;i++)
{
if(arr[i]==0&&ab[i]==1)
{
hea.push(node{i,0});
dis[i]=0;
}
}
hea.push(node{0,0});
dis[0]=0;
while(hea.size())
{
node ax=hea.top();
hea.pop();
now=ax.idx;
if(fin[now])
continue;
fin[now]=1;
for(i=head[now];i;i=a[i].nex)
{
if(dis[a[i].to]>(dis[now]+a[i].val)/a[i].typ)
{
dis[a[i].to]=(dis[now]+a[i].val)/a[i].typ;
if(!fin[a[i].to])
hea.push(node{a[i].to,dis[a[i].to]});
}
}
}
double ans=inf;
for(i=0;i<=K;i++)
ans=std::min(ans,dis[id(H,i)]);
return ans;
}
