#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ar array
const int N = 2e5 + 20;
namespace DSU{
int p[N];
void init(int n){
iota(p, p + n + 1, 0);
}
int find(int x){
if(p[x] == x)return x;
return p[x] = find(p[x]);
}
bool join(int u,int v){
u = find(u), v = find(v);
if(u == v)return 0;
p[u] = v;
return 1;
}
};
ld dist[N][100];
priority_queue<pair<ld, ar<int, 2> >, vector<pair<ld, ar<int, 2>>>, greater<pair<ld, ar<int, 2>>>> pq;
void push(int k,int x, ld d){
if(dist[x][k] > d){
dist[x][k] = d;
pq.push({d, {x, k}});
}
}
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> A) {
vector<ar<int, 2>> g[n];;
K = min(K, 69);
DSU::init(n);
for(int i = 0;i < m;i++){
if(x[i] != h && y[i] != h)DSU::join(x[i], y[i]);
g[x[i]].push_back({y[i], c[i]});
g[y[i]].push_back({x[i], c[i]});
}
ld pow[K + 1];
pow[0] = 1;
for(int i = 1;i <= K;i++)pow[i] = pow[i - 1] / 2;
A[0] = 0;
pq = priority_queue<pair<ld, ar<int, 2> >, vector<pair<ld, ar<int, 2>>>, greater<pair<ld, ar<int, 2>>>>();
for(int i = 0;i < n;i++){
for(int j = 0;j <= K;j++){
dist[i][j] = 1e18;
}
}
push(K, h, 0);
while(pq.size()){
ld d = pq.top().first;
auto [x, k] = pq.top().second;
pq.pop();
if(dist[x][k] < d)continue;
if(A[x] == 0)return d;
for(auto [u, c]: g[x]){
if(DSU::find(u) != DSU::find(0))continue;
push(k, u, d + c * pow[K - k]);
if(A[x] == 2 && k > 0)push(k - 1, u, d + c * pow[K - k + 1]);
}
}
return -1;
}
