#include <bits/stdc++.h>
const double EPS = 1e-10;
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 dist(n, std::vector<double>(k + 1, 1e18));
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]);
}
std::priority_queue<std::tuple<double, int, int>, std::vector<std::tuple<double, int, int>>, std::greater<>> pq;
dist[0][0] = 0;
pq.emplace(0, 0, 0);
while (pq.size()) {
auto [d, u, c] = pq.top();
pq.pop();
if (u == h) continue;
if (std::abs(dist[u][c] - d) > EPS) continue;
for (auto [to, w] : adj[u]) {
double nd = d + w;
if (arr[to] == 0) nd = 0;
if (dist[to][c] - EPS > nd) {
dist[to][c] = nd;
pq.emplace(nd, to, c);
}
if (arr[to] == 2 && c + 1 <= k && dist[to][c] - EPS > nd / 2) {
dist[to][c + 1] = nd / 2;
pq.emplace(nd / 2, to, c + 1);
}
}
}
double ans = *std::min_element(dist[h].begin(), dist[h].end());
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);
// }
