#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 ll INF = ll(1E18)+16;
vii adj[MAXN];
// priority queue of long long distance :smh:
// distance/=2 is like negative-weight edge , im using dijkstra :smh:
// solution: manage the thing only at the first level
// when reaching a 2-node, simulate the while(k--) dis /= 2 and then add the rest of dis to h
//
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 < 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();
for (auto [v, w] : adj[u]) {
if (vis[v]) continue;
vis[v] = true;
q.push(v);
}
}
if (!vis[h]) return -1;
vll disToH(n, INF);
vector <char> visToH(n, false);
disToH[h] = 0;
{priority_queue <ii> pq;
pq.push({ -disToH[h], h });
while (pq.size()) {
ll u = pq.top().second; pq.pop();
if (visToH[u]) continue;
visToH[u] = true;
for (auto [v, w] : adj[u]) {
if (!vis[v]) continue; // illegal
if (disToH[v] <= disToH[u]+w) continue;
disToH[v] = disToH[u]+w;
pq.push({ -disToH[v], v });
}
}}
priority_queue <ii> pq;
vll dis(n, INF);
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(n, false);
double den = 1;
for (ll i = 0; i < min(k, 60); i++) den *= 2;
double ans = INF;
while (pq.size()) {
ll u = pq.top().second; pq.pop();
if (vis[u]) continue;
vis[u] = true;
if (arr[u] == 2) {
ans = min(ans, dis[u]/den + double(disToH[u]));
} else {
ans = min(ans, double(dis[u] + disToH[u]));
}
if (u == h) continue; // once you reach cyberland you cannot move
for (auto [v, w] : adj[u]) {
if (dis[v] <= dis[u]+w) continue;
dis[v] = dis[u]+w;
pq.push({ -dis[v], v });
}
}
return ans;
}
