#include<bits/stdc++.h>
using namespace std;
#include "cyberland.h"
const int maxK=68;
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));
vector<bool>visited(maxN,0);
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]);
}
queue<int>q;
q.emplace(0);
while(!q.empty()){
int nownode=q.front();
q.pop();
if(visited[nownode])continue;
visited[nownode]=1;
for(auto [tonode,todist]:edge[nownode]){
q.emplace(tonode);
}
}
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(visited[i]&&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[tonode]==2 && nowK<KK){
double neww=(dist[nownode][nowK]+todist)/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;
}
