#include "bits/stdc++.h"
#include "cyberland.h"
// #include "stub.cpp"
using namespace std;
#define ff first
#define ss second
vector <vector <pair <int, int>>> v;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
double ans = 1e16;
v.clear();
v.resize(n);
long long s = 0;
for(int i = 0; i < m; i++) {
s += c[i];
v[x[i]].push_back({y[i], c[i]});
v[y[i]].push_back({x[i], c[i]});
}
k = min(k, int(__lg(s) + 5));
vector <vector <double>> dis(n+1, vector <double> (k+1, 1e16));
dis[0][0] = 0;
priority_queue <pair<double, pair <int, int>>> q;
q.push({0, {0, 0}});
while(!q.empty()) {
double ds = -q.top().ff;
int i = q.top().ss.ff, cn = q.top().ss.ss;
q.pop();
if(i == h) ans = min(ans, ds);
if(dis[i][cn] != ds) continue;
for(auto [j, w] : v[i]) {
double dss = ds + w;
if(dis[j][cn] > ds + w) {
dis[j][cn] = dss;
q.push({-dis[j][cn], {j, cn}});
}
if(arr[j] == 0) {
dis[j][cn] = 0;
q.push({-dis[j][cn], {j, cn}});
}
if(arr[j] == 2 and cn < k) {
dss /= 2;
if(dis[j][cn] > dss) {
dis[j][cn] = dss;
q.push({-dis[j][cn], {j, cn+1}});
}
}
}
}
return ans;
}
