#include <vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
struct e{
	double f;
	bool g;
}h[100000][61];
struct m{
	int n,o;
	friend bool operator>(m p,m q)
	{
		return h[p.n][p.o].f>h[q.n][q.o].f;
	}
};
int b[100000],d[200000],hh[100000];
priority_queue<m,vector<m>,greater<m> >r;
bool ff[100000];
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) {
	int i,j,k,l,s,v,bb,cc,dd,ee,gg,ii,jj;
	double aa;
	m t,u,w,z;
	for (i=0;i<N;i++) b[i]=-1;
	for (j=0;j<M<<1;j+=2)
	{
		d[j]=b[x[j>>1]];
		b[x[j>>1]]=j;
		d[j^1]=b[y[j>>1]];
		b[y[j>>1]]=j^1;
	}
	for (k=0;k<N;k++) for (l=0;l<61;l++)
	{
		h[k][l].f=9999900000000000.0;
		h[k][l].g=0;
	}
	for (;!r.empty();r.pop());
	for (s=b[H];s>-1;s=d[s])
	{
		h[s&1?x[s>>1]:y[s>>1]][0].f=c[s>>1];
		t.n=s&1?x[s>>1]:y[s>>1];
		t.o=0;
		r.push(t);
		if (arr[s&1?x[s>>1]:y[s>>1]]==2)
		{
			h[s&1?x[s>>1]:y[s>>1]][1].f=c[s>>1];
			u.n=s&1?x[s>>1]:y[s>>1];
			u.o=1;
			r.push(u);
		}
	}
	for (;!r.empty();r.pop()) if (!h[r.top().n][r.top().o].g)
	{
		h[r.top().n][r.top().o].g=1;
		for (v=b[r.top().n];v>-1;v=d[v]) if ((v&1?x[v>>1]:y[v>>1])!=H)
		{
			if (h[r.top().n][r.top().o].f+c[v>>1]/pow(2,r.top().o)<h[v&1?x[v>>1]:y[v>>1]][r.top().o].f)
			{
				h[v&1?x[v>>1]:y[v>>1]][r.top().o].f=h[r.top().n][r.top().o].f+c[v>>1]/pow(2,r.top().o);
				w.n=v&1?x[v>>1]:y[v>>1];
				w.o=r.top().o;
				r.push(w);
			}
			if (arr[v&1?x[v>>1]:y[v>>1]]==2&&r.top().o<60&&h[r.top().n][r.top().o].f+c[v>>1]/pow(2,r.top().o)<h[v&1?x[v>>1]:y[v>>1]][r.top().o+1].f)
			{
				h[v&1?x[v>>1]:y[v>>1]][r.top().o+1].f=h[r.top().n][r.top().o].f+c[v>>1]/pow(2,r.top().o);
				z.n=v&1?x[v>>1]:y[v>>1];
				z.o=r.top().o+1;
				r.push(z);
			}
		}
	}
	if (!h[0][0].g) return -1;
	aa=9999900000000000.0;
	for (ee=0;ee<N;ee++) ff[ee]=0;
	ff[0]=1;
	gg=1;
	hh[0]=0;
	for (ii=0;ii<gg;ii++)
	{
		for (jj=b[hh[ii]];jj>-1;jj=d[jj]) if ((jj&1?x[jj>>1]:y[jj>>1])!=H&&!ff[jj&1?x[jj>>1]:y[jj>>1]])
		{
			ff[jj&1?x[jj>>1]:y[jj>>1]]=1;
			hh[gg++]=jj&1?x[jj>>1]:y[jj>>1];
		}
	}
	for (bb=0;bb<N;bb++) if ((!bb||!arr[bb])&&ff[bb])for (cc=0;cc<=min(K,60);cc++) aa=min(aa,h[bb][cc].f);
	if (K>60) for (dd=0;dd<N;dd++) if (ff[dd]) aa=min(aa,h[dd][60].f);
	return aa;
}

RT