#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ll long long
#define pb push_back
#define uwu 100005
vector<pair<int,int>>adj[uwu];
double noiki(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){int father[N];
ll int yol[N];
for(int i=0;i<N;i++){
father[i]=-1;
yol[i]=1000000000000000000;
}
priority_queue<tuple<ll int,int,int>> pq;
pq.push({(ll int)0,0,-1});
while(pq.size()){
ll int node,once, deg;
tie(deg,node,once)=pq.top();deg=-deg;
pq.pop();
if(arr[node]==0){
deg=0;
}
if(yol[node]<=deg)continue;
yol[node]=deg;
father[node]=once;
if(node==H)continue;
for(auto u:adj[node]){
ll int kim=u.first, lira=u.second+deg;
pq.push({-lira,kim,node});
}
}
for(int i=0;i<N;i++)adj[i].clear();
if(yol[H]==1000000000000000000)yol[H]=-1;
return (1.0)*(double)yol[H];
}
//double uc(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr);
double solve(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){
for(int i=0;i<M;i++){
adj[x[i]].pb({y[i],c[i]});
adj[y[i]].pb({x[i],c[i]});
}
int yes=0;
for(int i=0;i<N;i++){
if(arr[i]==2){
yes=1;break;
}
}
if(yes==0)return noiki(N, M, K, H,x, y, c, arr);
//if(N<=3) return uc(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr);
int a=-1,b=-1,cey=-1;
int kac=0,yer=0;;
for(int i=H;i>-1;i--){
if(arr[i]==0){
yer=i;
break;
}
if(kac>=K)continue;
if(arr[i]==2){
if(kac==0)a=i;
if(kac==1)b=i;
if(kac==2&&K%2==1)cey=i;
kac++;
}
}
if(yer==H)return 0.0;
int father[N];
double yol[N];
for(int i=0;i<N;i++){
father[i]=-1;
yol[i]=1000000000000000000;
}
priority_queue<tuple<double,int,pair<int,int>>> pq;
pq.push({-0.0,0,{-1,0}});
while(pq.size()){
ll int node,once,ka;double deg;
pair<int,int> aaa;
tie(deg,node,aaa)=pq.top();deg=-deg;
pq.pop();
once=aaa.first;ka=aaa.second;
if(arr[node]==0){
deg=0;
}
if(node==cey||node==a||node==b&&ka<K){
deg=deg/2;
ka++;
}
//cout<<node<<" "<<once<<" "<<ka<<" "<<deg<<"_"<<a<<" "<<b<<" "<<cey<<endl;
if(yol[node]<=deg)continue;
yol[node]=deg;
father[node]=once;
if(node==H)continue;
for(auto u:adj[node]){
int kim=u.first;double lira=u.second+deg;
if(kim<node&&(node>a||node<=b))continue;
pq.push({-lira,kim,{node,ka}});
}
}
for(int i=0;i<N;i++)adj[i].clear();
return yol[H];
}
