#include "cyberland.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define MAXN 100005
vector<int> edge[MAXN];
vector<int> lian[MAXN];
bool ok[MAXN];
double dis[70][MAXN][2];
bool vis[70][MAXN];
struct kkk{
	int id;
	int ceng;
	double w;
	int can;
	friend bool operator <(kkk ano1,kkk ano2){
		if(ano1.ceng == ano2.ceng)
		return ano1.w > ano2.w;
		else return ano1.ceng > ano2.ceng;
	}
};
priority_queue<kkk> qq;
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) {
	for(int i = 0; i < N; i++) edge[i].clear(),lian[i].clear();
    for(int i = 0; i < N; i++) ok[i] = 0; 
    for(int i = 0; i < M; i++){
    	edge[x[i]].push_back(y[i]);
    	edge[y[i]].push_back(x[i]);
    	lian[x[i]].push_back(c[i]);
		lian[y[i]].push_back(c[i]); 
	}
	queue<int> q; q.push(0);
	while(q.size()){
		int nowx = q.front(); q.pop();
		if(ok[nowx]) continue;
		ok[nowx] = 1;
		for(int v : edge[nowx]){
			q.push(v);
		}
	}
	if(!ok[H]) return -1;
	for(int i = 0; i <= K; i++){
		for(int j = 0; j <= N; j++) dis[i][j][0] = dis[i][j][1] = 1e17,vis[i][j] = 0;
	} 
	while(qq.size()) qq.pop();
	for(int i = 0; i < N; i++){
		if(arr[i] == 0 && ok[i] == 1){
			 qq.push((kkk){i,0,0,1});
			 dis[0][i][1] = 0;
		}
	}
	qq.push((kkk){0,0,0,1});
	dis[0][0][1] = 0;
	double ans = 1e17;
	int cengok[100];
	memset(cengok,0,sizeof(cengok));
	while(qq.size()){
		int nowx = qq.top().id,ceng = qq.top().ceng,can = qq.top().can; qq.pop();
		if(vis[ceng][nowx]) continue;
		vis[ceng][nowx] = 1;
		if(nowx % N == H && !cengok[ceng]) {
			ans = min(ans,min(dis[ceng][nowx][0],dis[ceng][nowx][1]));
			cengok[ceng] = 1;
			continue;
		}
		if(arr[nowx] == 2 && dis[ceng+1][nowx][0] > dis[ceng][nowx][1] / 2.0 && ceng < K){
			dis[ceng+1][nowx][0] = dis[ceng][nowx][1] / 2.0;
			qq.push((kkk){nowx,ceng+1,dis[ceng+1][nowx][0],0});
		}
		for(int vv = 0; vv < edge[nowx].size(); vv++){
			int v = edge[nowx][vv];
				if(dis[ceng][v][1] > min(dis[ceng][nowx][0],dis[ceng][nowx][1]) + lian[nowx][vv]){
					dis[ceng][v][1] = min(dis[ceng][nowx][0],dis[ceng][nowx][1]) + lian[nowx][vv];
					qq.push((kkk){v,ceng,dis[ceng][v][1],1});
				}
		}
	}
	return ans;
}