#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using pr = pair<int, int>;
using tri = tuple<double, int, int>;
const double INF = 1e18 + 7;
vector<vector<pr>> edge;
vector<bool> vis;
int h;
void dfs(int node) {
if (vis[node]) return;
vis[node] = 1;
for (auto [next, w] : edge[node]) {
if (next == h) continue;
dfs(next);
}
}
double solve(int n, int m, int k, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
h = H;
k = min(50, k);
edge.assign(n, {});
vis.assign(n, 0);
for (int i = 0; i < m; i++) {
int a = x[i], b = y[i], w = c[i];
edge[a].pb({b, w});
edge[b].pb({a, w});
}
priority_queue<tri, vector<tri>, greater<tri>> q; // dist, k, node
vector<vector<double>> dp(k+1, vector<double>(n, INF));
q.push({0, 0, 0});
dp[0][0] = 0;
dfs(0);
for (int i = 1; i < n; i++) {
if (vis[i] && arr[i] == 0) {
dp[0][i] = 0;
q.push({0, 0, i});
}
}
while (!q.empty()) {
auto [cur, use, node] = q.top(); q.pop();
if (cur > dp[use][node] || node == h) continue;
for (auto [next, w] : edge[node]) {
if (arr[next] == 0) continue;
if (dp[use][next] > cur + w) {
dp[use][next] = cur + w;
q.push({cur + w, use, next});
}
double d = (cur + w) / 2;
if (arr[next] == 2 && use < k && dp[use + 1][next] > d) {
dp[use + 1][next] = d;
q.push({d, use + 1, next});
}
}
}
double res = INF;
for (int i = 0; i <= k; i++) {
// for (int j = 0; j < n; j++)
// cout << dp[i][j] << ' ';
// cout << '\n';
res = min(res, dp[i][h]);
}
if (res == INF) return -1;
else return res;
}
