#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
// #define int long long
#define ll long long
#define ff first
#define ss second
#define pint pair < double , int >
#define vint vector < int >
#define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL)
const double inf = 1e18 + 9;
const int mxn = 2e5 + 2;
const int mod = 1e9 + 7;
vector < vector < pint > > adj(mxn);
vint arr_;
double dis[77][mxn];
bool vis[mxn];
priority_queue < pint > q[77];
void dfs(int x , int par , int H) {
if (vis[x]) return;
vis[x] = 1;
if (x == H) return;
if (arr_[x] == 0) q[0].push({0 , x});
for (pint i : adj[x]) {
if (i.ss == par) continue;
dfs(i.ss , x , H);
}
}
double solve(int n , int m , int k , int H , vint x , vint y , vint c , vint arr) {
for (int i = 0; i < n; i++) {
adj[i].clear();
vis[i] = 0;
}
k = min(k , 75);
for (int i = 0; i <= k; i++) {
for (int j = 0; j < n; j++) {
dis[i][j] = -1;
}
}
arr_ = arr;
for (int i = 0; i < m; i++) {
adj[x[i]].push_back({c[i] , y[i]});
adj[y[i]].push_back({c[i] , x[i]});
}
dfs(0 , 0 , H);
q[0].push({0 , 0});
for (int i = 0; i <= k; i++) {
for(int u = 0; i < n; u++)
vis[u] = 0;
while (!q[i].empty()) {
pint p = q[i].top();
q[i].pop();
if (vis[p.ss]) continue;
vis[p.ss] = 1;
dis[i][p.ss] = -p.ff;
if (p.ss == H) continue;
for (pint j : adj[p.ss]) {
if (arr[j.ss] == 0) continue;
q[i].push({p.ff - j.ff , j.ss});
if (arr[j.ss] == 2) q[i+1].push({(p.ff - j.ff) / 2.0 , j.ss});
}
}
}
double ans = inf;
for (int i = 0; i <= k; i++) {
if (dis[i][H] != -1) ans = min(ans , dis[i][H]);
}
if (ans == inf) return -1;
return ans;
}
