#include "cyberland.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using ld = long double;
using diii = tuple<ld, int, int, bool>;
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define ppb pop_back
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
K = min(K, 1000);
bool vis[N];
ld dist[N][K + 1][2];
vector<ii> adj[N];
queue<int> Q;
priority_queue<diii, vector<diii>, greater<diii> > pq;
for (int i = 0; i < N; i++) {
vis[i] = 0;
for (int j = 0; j <= K; j++) {
dist[i][j][0] = dist[i][j][1] = (ld)1e18;
}
}
for (int i = 0; i < M; i++) {
adj[x[i]].eb(y[i], c[i]);
adj[y[i]].eb(x[i], c[i]);
}
vis[0] = 1;
Q.push(0);
while (!Q.empty()) {
int v = Q.front();
Q.pop();
for (auto [u, w] : adj[v]) {
if (!vis[u] && u != H) {
vis[u] = 1;
Q.push(u);
}
}
}
for (int i = 0; i < N; i++) {
if (vis[i] && (arr[i] == 0 || i == 0)) {
dist[i][K][0] = dist[i][K][1] = 0;
pq.emplace(0, i, K, 0);
}
}
while (!pq.empty()) {
auto [d, v, k, jd] = pq.top();
pq.pop();
if (d != dist[v][k][jd]) continue;
if (v == H) continue;
if (arr[v] == 2 && k && !jd) {
if (d / (ld)2 < dist[v][k - 1][1]) {
dist[v][k - 1][1] = d / (ld)2;
pq.emplace(dist[v][k - 1][1], v, k - 1, 1);
}
}
for (auto [u, w] : adj[v]) {
if (d + w < dist[u][k][0]) {
dist[u][k][0] = d + w;
pq.emplace(dist[u][k][0], u, k, 0);
}
}
}
ld ret = min(dist[H][0][0], dist[H][0][1]);
for (int i = 1; i <= K; i++) ret = min({ret, dist[H][i][0], dist[H][i][1]});
return ret == (ld)1e18 ? -1 : ret;
}
