#include "cyberland.h"
#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();
	K=std::min(K,72);
	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;
}