#include "cyberland.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,apio=b;i<apio;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto slkdh:v)cout<<slkdh<<" ";cout<<"\n"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
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) {
ll n=N,m=M,h=H,k=K;
vector<ll>a(n);
fore(i,0,n)a[i]=arr[i];
vector<ii>g[n];
fore(i,0,m){
g[x[i]].pb({y[i],c[i]});
g[y[i]].pb({x[i],c[i]});
}
ld d[n][k+5];
fore(i,0,n)fore(j,0,k+5)d[i][j]=-1;
priority_queue<pair<ld,ii>>pq;
a[0]=0;
fore(i,0,n)if(!a[i]){
pq.push({0,{i,0}});
d[i][0]=0;
}
while(SZ(pq)){
auto [w,par]=pq.top(); pq.pop(); w=-w;
auto [x,u]=par;
if(d[x][u]<w)continue;
//cout<<x<<" "<<u<<": "<<w<<"\n";
for(auto [y,w]:g[x]){
ld nd=d[x][u]+w;
if(d[y][u]==-1||nd<d[y][u])
d[y][u]=nd,pq.push({-nd,{y,u}});
if(a[y]==2){
nd/=2.0;
ll v=u+1;
if(v>k)continue;
if(d[y][v]==-1||nd<d[y][v])
d[y][v]=nd,pq.push({-nd,{y,v}});
}
}
}
ld res=-1;
fore(i,0,k+1){
//cout<<i<<" "<<d[h][i]<<"\n";
if(d[h][i]!=1&&(res==-1||d[h][i]<res))res=d[h][i];
}
return res;
}
