#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;
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;
dist[0][min(K,maxK)]=0;
pq.emplace(make_pair(0,min(K,maxK)),0);
while(!pq.empty()){
auto[AAA,nownode]=pq.top();
auto[nowdist,nowK]=AAA;
pq.pop();
if(nowdist>dist[nownode][nowK])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(nowK>0){
if(arr[nownode]==0){
if(dist[tonode][nowK-1]>todist){
dist[tonode][nowK-1]=todist;
pq.emplace(make_pair(dist[tonode][nowK-1],nowK-1),tonode);
}
}
else if(arr[nownode]==2){
if(dist[tonode][nowK-1]>dist[nownode][nowK]/2+todist){
dist[tonode][nowK-1]=dist[nownode][nowK]/2+todist;
pq.emplace(make_pair(dist[tonode][nowK-1],nowK-1),tonode);
}
}
}
}
}
double out=inf;
for(int i=0;i<=maxK;++i){
if(dist[H][i]<out)
out=dist[H][i];
}
if(out==inf)out=-1;
return out;
}
