#include <bits/stdc++.h>
using namespace std;
/*
*/
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
const int MAXN = 1e5+10, MAXK = 30+15;
const long long BIG = 1e18+8;
const long double PRECISION = 1e-7;
vector<pair<int, long double>> e[MAXN];
long double ds[MAXN][MAXK];
bool r[MAXN];
void dfs(int x){
r[x] = 1;
for (auto &[i,cst]:e[x]) if (!r[i]) dfs(i);
}
double solve(int n, int m, int k, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
for (int i=0;i<n;i++){
e[i].clear();
for (int j=0;j<=k;j++) ds[i][j]=BIG;
r[i] = 0;
}
for (int i=0;i<m;i++){
int a = x[i], b = y[i];
e[a].emplace_back(b, c[i]);
e[b].emplace_back(a,c[i]);
}
dfs(0);
typedef tuple<long double, int, int> node; // {dst, qntk, u}
priority_queue<node, vector<node>, greater<>> q;
for (int i=0;i<n;i++) if (!i || (r[i] && arr[i]==0)){
ds[i][0] = 0;
q.emplace(0, 0, i);
}
while (!q.empty()){
auto [d, qk, u] = q.top();
q.pop();
if (u == H) continue;
for (auto &[i, cs]:e[u]){
long double nc = d+cs;
// sem usar
if (ds[i][qk]>nc){
ds[i][qk] = nc;
q.emplace(nc, qk, i);
}
// usando
nc /= 2.00;
if (qk<k && arr[i] == 2 && ds[i][qk+1]> nc){
ds[i][qk+1] = nc;
q.emplace(nc, qk+1, i);
}
}
}
long double ans = BIG;
for (int i=0;i<=k;i++) ans = min(ans, ds[H][i]);
// cerr << ds[1][4] << '\n';
if (ans == BIG) return -1;
return ans;
}
