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