#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define db double
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio\
ios_base::sync_with_stdio(0);\
cin.tie(0);\
cout.tie(0)\
#define pdi pair<db, int>
const int sz = 1e5;
const db inf = 1e14;
const db eps = 1e-7;
int n, m, k, h;
db d[sz][70];
bool used[sz];
vector<pair<int, double>> g[sz];
void dfs(int node){
used[node] = true;
for(auto i : g[node]){
if(used[i.first]) continue;
dfs(i.first);
}
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
n = N, m = M, k = K, h = H;
k = min(69, k);
for(int i = 1; i <= n; i++){
used[i] = false;
for(int j = 0; j <= k; j++){
d[i][j] = inf;
}
}
for(int i = 0; i < m; i++){
g[x[i] + 1].push_back({y[i] + 1, c[i]});
g[y[i] + 1].push_back({x[i] + 1, c[i]});
}
dfs(1);
priority_queue<pair<pdi, int>, vector<pair<pdi, int>>, greater<pair<pdi, int>>> pq;
d[1][0] = 0;
pq.push({{0.0, 0}, 1});
for(int i = 2; i <= n; i++){
if(arr[i - 1] == 0 and used[i]) d[i][0] = 0, pq.push({{0.0, 0}, i});
}
while(!pq.empty()){
int cur = pq.top().second, cr = pq.top().first.second;
if(d[cur][cr] - pq.top().first.first < -eps){
pq.pop();
continue;
}
pq.pop();
for(auto i : g[cur]){
if(d[i.first][cr] - d[cur][cr] - i.second > eps){
d[i.first][cr] = d[cur][cr] + i.second;
pq.push({{d[i.first][cr], cr}, i.first});
}
if(arr[cur - 1] == 2 and cr + 1 <= k){
if(d[i.first][cr + 1] - (d[cur][cr] + i.second) / 2.0 > eps){
d[i.first][cr + 1] = (d[cur][cr] + i.second) / 2.0;
pq.push({{d[i.first][cr + 1], cr + 1}, i.first});
}
}
}
}
// for(int i = 1; i <= n; i++){
// for(int j = 0; j <= k; j++){
// cout << d[i][j] << " ";
// }
// cout << endl;
// }
db res = inf;
for(int i = 0; i <= k; i++){
// cout << d[H + 1][i] << " ";
res = min(res, d[H + 1][i]);
}
return (res == inf ? -1 : res);
}
