#include <bits/stdc++.h>
using namespace std;
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){
vector<pair<int,long double> > adj[N];
int n=N,m=M,k=K,h=H;
int sz=80;
k=min(k,sz-1);
for(int i=0; i<m; i++){
adj[x[i]].push_back({y[i],c[i]});
adj[y[i]].push_back({x[i],c[i]});
}
int can[n];
memset(can,0,sizeof(can));
queue<int> q;
q.push(0);
while(!q.empty()){
int a=q.front();
q.pop();
if(can[a]) continue;
can[a]=1;
for(auto i:adj[a]){
if(!can[i.first]&&i.first!=h) q.push(i.first);
if(i.first==h) can[h]=1;
}
}
if(!can[h]) return -1;
long double dist[k+5][n];
for(int j=0; j<k+5; j++) for(int i=0; i<n; i++) dist[j][i]=1e16;
priority_queue<pair<long double,int>,vector<pair<long double,int>>,greater<pair<long double,int> > > pq[k+5];
pq[0].push({0,0});
for(int i=1; i<n; i++){
if(arr[i]==0&&can[i]){
pq[0].push({0,i});
}
}
for(int i=0; i<=k; i++){
if(i){
for(int j=0; j<n; j++) dist[i][j]=min(dist[i][j],dist[i-1][j]);
for(int j=0; j<n; j++) if(can[j]) pq[i].push({dist[i][j],j});
}
while(!pq[i].empty()){
long double a=pq[i].top().first;
int b=pq[i].top().second;
pq[i].pop();
if(dist[i][b]<a) continue;
dist[i][b]=a;
if(b==h) continue;
long double cc=a/(long double)2.0;
for(auto j:adj[b]){
if(dist[i][j.first]>a+j.second){
pq[i].push({a+j.second,j.first});
}
if(i<k&&arr[b]==2){
if(dist[i+1][j.first]>cc+j.second){
dist[i+1][j.first]=cc+j.second;
}
}
}
}
}
return (double)dist[k][h];
}/*
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout << solve(3,3,1,2,{0,0,1},{1,2,2},{10000,500000,1},{1,2,1});
}*/
