#include "cyberland.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define MAXN 7000005
vector<int> edge[MAXN];
vector<int> lian[MAXN];
bool ok[MAXN];
double dis[MAXN];
bool vis[MAXN];
struct kkk{
	int id;
	double w;
	friend bool operator <(kkk ano1,kkk ano2){
		return ano1.w > ano2.w;
	}
};
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) {
    K = 0;
	for(int i = 0; i < (K+1) * 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 < N; i++){
		for(int j = 0; j < K; j++){
			edge[j * N + x[i]].push_back((j + 1) * N + x[i]);
			lian[j * N + x[i]].push_back(-114514);
		}
	}
	for(int i = 0; i < (K+1) * N; i++) dis[i] = 1e17,vis[i] = 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});
			 dis[i] = 0;
		}
	}
	qq.push((kkk){0,0});
	dis[0] = 0;
	double ans = 1e17;
	while(qq.size()){
		int nowx = qq.top().id; qq.pop();
		if(vis[nowx]) continue;
		vis[nowx] = 1;
		if(nowx % N == H) ans = min(ans,dis[nowx]);
		for(int vv = 0; vv < edge[nowx].size(); vv++){
			int v = edge[nowx][vv];
			if(lian[nowx][vv] == -114514){
				if(dis[v] > (double)dis[nowx] / 2.0){
					dis[v] = (double)dis[nowx] / 2.0;
					qq.push((kkk){v,dis[v]});
				}
			}else{
				if(dis[v] > dis[nowx] + lian[nowx][vv]){
					dis[v] = dis[nowx] + lian[nowx][vv];
					qq.push((kkk){v,dis[v]});
				}
			}
		}
	}
	return ans;
}