#include <bits/stdc++.h>
using namespace std;
double solve(
int N, int M, int K, int H,
vector<int> x,
vector<int> y,
vector<int> c,
vector<int> arr
) {
const double INF = 1e18;
// граф
vector<vector<pair<int,double>>> g(N);
for (int i = 0; i < M; i++) {
g[x[i]].push_back({y[i], c[i]});
g[y[i]].push_back({x[i], c[i]});
}
// dp[k][v] = минимальное время
vector<vector<double>> dp(K + 1, vector<double>(N, INF));
priority_queue<
pair<double, pair<int,int>>,
vector<pair<double, pair<int,int>>>,
greater<>
> pq;
dp[0][0] = 0;
pq.push({0, {0, 0}});
while (!pq.empty()) {
auto [dist, state] = pq.top();
pq.pop();
int v = state.first;
int used = state.second;
if (dp[used][v] != dist) continue;
// способность arr[v] = 0 (обнуление)
if (arr[v] == 0 && dist > 0) {
if (dp[used][v] > 0) {
dp[used][v] = 0;
pq.push({0, {v, used}});
}
}
for (auto [u, w] : g[v]) {
double nd = dist + w;
// обычный переход
if (dp[used][u] > nd) {
dp[used][u] = nd;
pq.push({nd, {u, used}});
}
// деление на 2
if (arr[u] == 2 && used < K) {
double nd2 = nd * 0.5;
if (dp[used + 1][u] > nd2) {
dp[used + 1][u] = nd2;
pq.push({nd2, {u, used + 1}});
}
}
}
}
double ans = INF;
for (int i = 0; i <= K; i++) {
ans = min(ans, dp[i][H]);
}
if (ans >= INF / 2) return -1;
return ans;
}
