#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::queue<std::pair<double, int>> pq;
for (int i = 0; i < n; ++i) {
pq.emplace(dist[i], i);
}
while (pq.size()) {
auto [d, u] = pq.front();
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;
}
// int main() {
// int n, m, k, h;
// std::cin >> n >> m >> k >> h;
// std::vector<
// std::vector<int> a(n);
// for (auto& i : a) std::cin >> i;
// std::cout << sequence(n, a);
// }
