#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
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], vw[i] });
adj[v[i]].push_back({ u[i], 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 <double, ll> > pq;
dis[0] = 0;
pq.push({ 0, 0 });
for (ll u = 1; u < n; u++) {
if (vis[u] && arr[u] == 0) {
dis[u] = 0;
pq.push({ 0, u });
}
}
vis.assign(31*n, false);
while (pq.size()) {
ll ou = pq.top().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;
if (lvl < 30 && arr[u] == 2) { // do the /2 thingy
for (auto [v, w] : adj[u]) {
ll ov = v+(lvl+1)*n;
if (dis[ov] <= dis[ou]/2) continue;
dis[ov] = dis[ou]/2;
pq.push({ -dis[ov], ov });
}
}
for (auto [v, w] : adj[u]) {
ll ov = v+lvl*n;
if (dis[ov] <= dis[ou]+w) continue;
dis[ov] = dis[ou]+w;
pq.push({ -dis[ov], ov });
}
}
double ans = INF;
for (ll i = 0; i <= k; i++) {
ans = min(ans, dis[h+i*n]);
}
return ans;
}
