#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using id = pair <ll, double>;
using vii = vector <id>;
const ll MAXN = 1E5+16;
const double INF = double(1E18)+16;
vii adj[MAXN];
double dis[31*MAXN];
double solve (int n, int m, int k, int h, vi u, vi v, vi vw, vi arr) {
fill(adj, adj+n, vii({}));
for (ll i = 0; i < 31*n; i++) dis[i] = INF;
for (ll i = 0; i < m; i++) {
adj[u[i]].push_back({ v[i], double(vw[i]) });
adj[v[i]].push_back({ u[i], double(vw[i]) });
}
vector <char> vis(n, false);
queue <ll> q;
q.push(0);
vis[0] = true;
while (q.size()) {
ll u = q.front(); q.pop();
if (u == h) continue;
for (auto [v, w] : adj[u]) {
if (vis[v]) continue;
vis[v] = true;
q.push(v);
}
}
if (!vis[h]) return -1;
priority_queue <pair <ll, pair <double, ll> > > pq;
dis[0] = 0;
pq.push({ 0, { 0, 0 } });
for (ll u = 1; u < n; u++) {
if (vis[u] && arr[u] == 0) {
dis[u] = 0;
pq.push({ 0, { 0, u } });
}
}
vis.assign(31*n, false);
while (pq.size()) {
ll ou = pq.top().second.second; pq.pop();
if (vis[ou]) continue;
vis[ou] = true;
ll u = ou%n;
if (u == h) continue; // once you reach cyberland you cannot move
ll lvl = ou/n;
for (auto [v, w] : adj[u]) {
ll ov = v+lvl*n;
if (arr[v] == 2 && lvl < 30) {
if (dis[ov+n] > (dis[ou]+w)/2) {
dis[ov+n] = (dis[ou]+w)/2;
pq.push({ -(lvl+1), { -dis[ov+n], ov+n } });
}
}
if (dis[ov] <= dis[ou]+w) continue;
dis[ov] = dis[ou]+w;
pq.push({ -lvl, { -dis[ov], ov } });
}
}
double ans = INF;
for (ll i = 0; i <= k; i++) {
ans = min(ans, dis[h+i*n]);
}
return ans;
}
