#pragma GCC optimize("Ofast,O1,O2,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, double>>> g;
vector<bool> used;
vector<int> zeros;
void dfs(int v, const vector<int> &arr){
used[v] = true;
if (arr[v] == 0 || v == 0) zeros.push_back(v);
for (auto [u, w] : g[v]){
if (!used[u]){
dfs(u, arr);
}
}
}
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) {
K = min(K, 70);
g.clear();
g.resize(N);
for (int i = 0; i < M; i++) {
if (y[i] != H) g[x[i]].emplace_back(y[i], c[i]);
if (x[i] != H) g[y[i]].emplace_back(x[i], c[i]);
}
zeros.clear();
used.assign(N, false);
dfs(0, arr);
const double INF = 2e15;
vector<vector<double>> dp(N, vector<double>(K + 1, INF));
for (int v : zeros){
dp[v].assign(K + 1, 0);
}
double ans = INF;
for (int k = 0; k <= K; k++) {
if (k > 0) {
for (int i = 0; i < N; i++) {
if (dp[i][k - 1] == INF) continue;
dp[i][k] = min(dp[i][k], dp[i][k - 1]);
if (arr[i] == 0) {
dp[i][k] = 0;
}
}
}
priority_queue<pair<double, int>> pq;
for (int i = 0; i < N; i++) {
if (dp[i][k] != INF) pq.emplace(-dp[i][k], i);
}
vector<bool> processed(N, false);
while (!pq.empty()) {
int v = pq.top().second;
pq.pop();
if (processed[v]) continue;
processed[v] = true;
for (auto [u, w]: g[v]) {
double new_val = dp[v][k] + w;
if (arr[u] == 0) new_val = 0;
if (arr[u] == 2 && k < K) {
dp[u][k + 1] = min(dp[u][k + 1], (dp[v][k] + w) / 2);
}
if (dp[u][k] > new_val) {
dp[u][k] = new_val;
pq.emplace(-dp[u][k], u);
}
}
}
for (auto [v, w]: g[H]) {
if (dp[v][k] == INF) continue;
if (arr[H] == 0) return 0;
ans = min(ans, dp[v][k] + w);
if (k < K && arr[H] == 2) {
ans = min(ans, (dp[v][k] + w) / 2);
}
}
}
if (ans == INF) return -1;
return ans;
}
