#include<bits/stdc++.h>
using namespace std;
#include "cyberland.h"
const int maxK=67;
const double inf=4e18;
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) {
const int maxN=N+1;
const int KK=min(K,maxK);
vector<pair<int,int>>edge[maxN];
vector<vector<double>>dist(maxN,vector<double>(maxK+1,inf));
for(int i=0;i<M;++i){
edge[x[i]].emplace_back(y[i],c[i]);
edge[y[i]].emplace_back(x[i],c[i]);
}
priority_queue<pair<pair<double,int>,int>,vector<pair<pair<double,int>,int>>,greater<pair<pair<double,int>,int>>>pq;
for(int i=0;i<N;++i){
if(arr[i]==0)dist[i][0]=0;
pq.emplace(make_pair(0,0),i);
}
dist[0][0]=0;
pq.emplace(make_pair(0,0),0);
while(!pq.empty()){
auto[AAA,nownode]=pq.top();
auto[nowdist,nowK]=AAA;
pq.pop();
if(nowdist>dist[nownode][nowK])continue;
if(nownode==H)continue;
for(auto [tonode,todist]:edge[nownode]){
if(dist[tonode][nowK]>dist[nownode][nowK]+todist){
dist[tonode][nowK]=dist[nownode][nowK]+todist;
pq.emplace(make_pair(dist[tonode][nowK],nowK),tonode);
}
if(arr[nownode]==2 && nowK<KK){
double neww=dist[nownode][nowK]/2.0;
if(dist[tonode][nowK+1]>neww){
dist[tonode][nowK+1]=neww;
pq.emplace(make_pair(neww,nowK+1),tonode);
}
}
}
}
double out=inf;
for(int i=0;i<=KK;++i){
if(dist[H][i]<out)
out=dist[H][i];
}
if(out==inf)out=-1;
return out;
}
