#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
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) {
vector<vector<pair<int, int>>> adj(N);
for(int i = 0; i < M; ++i) {
adj[x[i]].emplace_back(y[i], c[i]);
adj[y[i]].emplace_back(x[i], c[i]);
}
vector<double> dist(N, DBL_MAX);
priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> dijkstra;
dijkstra.emplace(0, H, 0);
arr[0] = -1;
queue<int> bfs; bfs.push(0);
vector<bool> visited_0(N);
while(!bfs.empty()) {
int u = bfs.front(); bfs.pop();
if(visited_0[u]) continue;
visited_0[u] = true;
if(arr[u] == 0) arr[u] = -1;
if(u == H) continue; // we can't move from H
for(auto [v, c]: adj[u]) bfs.push(v);
}
double min_dist = DBL_MAX;
while(!dijkstra.empty()) {
auto [d, u, k] = dijkstra.top();
dijkstra.pop();
if(d >= dist[u]) continue;
dist[u] = d;
if(arr[u] == -1) {
min_dist = min(min_dist, d);
} else if(arr[u] == 2 && k < K) {
++k;
}
for(auto [v, cv]: adj[u]) {
dijkstra.emplace(d + (double)cv/(1 << k), v, k);
}
}
if(min_dist == DBL_MAX) return -1;
return min_dist;
}
