#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
#define ld double
#define pii pair<int,int>
#define ll long long
#define rep(i,a,b) for(int i = a; i <= b; i++)
const int MAXN = 1e5+10;
bool mk[MAXN];
ld pwr[72];
void dfs(int u, vector<vector<pii>> &g, int H) {
if(mk[u]) return;
if (u==H) return;
mk[u] = 1;
for(auto &[v,w] : g[u]) dfs(v,g,H);
}
using z = pair<ld, pair<int,int>>;
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) {
K=min(K,70);
rep(i,0,N-1) mk[i] = 0;
vector<vector<ld>> dist(N, vector<ld>(K+1,1e18));
vector<vector<pii>> g(N);
pwr[0] = 1;
rep(i,1,K) pwr[i] = pwr[i-1]/2.0;
rep(i,0,M-1) {
g[x[i]].emplace_back(y[i],c[i]);
g[y[i]].emplace_back(x[i],c[i]);
}
dfs(0,g,H);
arr[0] = 0;
priority_queue<z,vector<z>,greater<z>> pq;
dist[H][0] = 0;
pq.push({0,{H,0}});
while (!pq.empty()) {
auto [d,h] = pq.top();pq.pop();
int u = h.first;
int ck = h.second;
if(dist[u][ck] < d) continue;
if(arr[u] == 0) return d;
for(auto &[v,w] : g[u]) {
if(!mk[v]) continue;
ld nd = d+w*pwr[ck];
int cck = ck;
if(nd < dist[v][cck]) {
dist[v][cck] = nd;
pq.push({nd,{v,cck}});
}
if(arr[u] == 2 && cck < K) cck++;
nd = d + w*pwr[cck];
if(nd < dist[v][cck]) {
dist[v][cck] = nd;
pq.push({nd,(pii){v,cck}});
}
}
}
return -1;
}
