#pragma GCC optimize("O3,unroll-loops")
#ifndef Local
#include "cyberland.h"
#endif
#include <bits/stdc++.h>
using namespace std;
const int lim=1e5+10;
const double inf=2e30;
using pii=pair<int,int>;
using pdi=pair<double,int>;
vector<pii> v[lim];
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) {
int n=N,m=M,k=K,h=H;
for(int i=0;i<m;i++){
v[x[i]].push_back({y[i],c[i]});
v[y[i]].push_back({x[i],c[i]});
}
double *dist[2];
dist[0]=new double[n];
dist[1]=new double[n];
for(int i=0;i<n;i++){
dist[0][i]=arr[i]?inf:0;
}
priority_queue<pdi,vector<pdi>,greater<pdi>>pq;
for(int i=0;i<n;i++){
if(!arr[i]){
pq.push({0,i});
}
}
if(arr[0]){
dist[0][0]=0;
pq.push({0,0});
}
double ans=inf;
for(int rp=0;rp<min(k,100);rp++){
ans=min(ans,dist[0][h]);
for(int i=0;i<n;i++){
dist[1][i]=arr[i]?inf:0;
}
while(pq.size()){
auto nn=pq.top();
pq.pop();
double cost=nn.first;
int node=nn.second;
if(cost!=dist[0][node])continue;
if(arr[node]==2){
dist[1][node]=min(dist[1][node],cost/2);
}
for(auto j:v[node]){
dist[1][j.first]=min(dist[1][j.first],cost+j.second);
}
}
for(int i=0;i<n;i++){
pq.push({dist[1][i],i});
}
swap(dist[0],dist[1]);
}
ans=min(ans,dist[0][h]);
return ans;
}
#ifdef Local
int main(){
cout<<solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1})<<"\n";
}
#endif
