#include <bits/stdc++.h>
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 = std::min(k, 60);
std::vector<std::vector<std::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]);
}
double ans = 1e18;
std::vector<double> dist(n, 1e18);
dist[0] = 0;
for (int iter = 0; iter <= k; ++iter) {
std::vector<double> ndist(n, 1e18);
std::priority_queue<std::pair<double, int>, std::vector<std::pair<double, int>>, std::greater<>> pq;
for (int i = 0; i < n; ++i) {
if (dist[i] < 1e17) pq.emplace(dist[i], i);
}
while (pq.size()) {
auto [d, u] = pq.top();
pq.pop();
if (u == h) continue;
if (d > dist[u]) continue;
for (auto [to, w] : adj[u]) {
double nd = d + w;
if (arr[to] == 0) nd = 0;
if (dist[to] > nd) {
pq.emplace(dist[to] = nd, to);
}
if (arr[to] == 2) {
ndist[to] = std::min(ndist[to], nd / 2);
}
}
}
ans = std::min(ans, dist[h]);
dist = ndist;
}
if (ans > 1e17) return -1;
return ans;
}
