#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<bool> isReachable;
void dfs(ll v, ll H, vector<vector<pair<ll,ll>>>& adj) {
isReachable[v] = true;
if(v == H) return;
for(auto u : adj[v]) {
if(!isReachable[u.first]){
dfs(u.first, H, adj);
}
}
}
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<ll,ll>>> adj(N);
isReachable.clear();
isReachable.resize(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]);
}
dfs(0, H, adj);
if(!isReachable[H]) return -1;
K = min(K, 60);
vector<double> pwr(K + 1, 1);
for (int i = 1; i <= K; i++)
pwr[i] = pwr[i - 1] / 2;
arr[0] = 0;
vector<vector<double>> dist(K + 1, vector<double>(N, 1e18));
using node = tuple<double, int, int>;
priority_queue<node, vector<node>, greater<node>> pq;
auto enq = [&](int k, int x, double d) {
if (dist[k][x] > d) {
dist[k][x] = d;
pq.push({d, k, x});
}
};
enq(K, H, 0);
while (!pq.empty()) {
auto [d, k, v] = pq.top();
pq.pop();
if (dist[k][v] < d)
continue;
if (arr[v] == 0)
return d;
for (auto &[w, c] : adj[v]) {
if (!isReachable[w])
continue;
enq(k, w, d + c * pwr[K - k]);
if (arr[v] == 2 && k > 0) {
enq(k - 1, w, d + c * pwr[K - k + 1]);
}
}
}
return -1;
}
