#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
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) {
const long double INF = 1e30L;
vector<vector<pair<int, int>>> 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]});
}
vector<vector<long double>> dis(
N,
vector<long double>(K + 1, INF));
using T = tuple<long double, int, int>;
priority_queue<T, vector<T>, greater<T>> pq;
dis[0][0] = 0;
pq.emplace(0.0L, 0, 0);
auto relax = [&](int v, int used, long double nd) {
if (nd < dis[v][used]) {
dis[v][used] = nd;
pq.emplace(nd, v, used);
}
};
while (!pq.empty()) {
auto [d, u, used] = pq.top();
pq.pop();
if (d > dis[u][used])
continue;
for (auto [v, w] : g[u]) {
long double nd = d + w;
relax(v, used, nd);
if (arr[v] == 0) {
relax(v, used, 0.0L);
}
if (arr[v] == 2 && used < K) {
relax(v, used + 1, nd / 2.0L);
}
}
}
long double ans = INF;
for (int k = 0; k <= K; k++) {
ans = min(ans, dis[H][k]);
}
if (ans >= INF / 2)
return -1;
return (double)ans;
}
