#include <bits/stdc++.h>
//#include "cyberland.h"
using i64 = long long;
struct DSU {
int n;
std::vector<int> par;
DSU(int _n) : n(_n) {
par.resize(n);
std::iota(par.begin(), par.end(), 0);
}
int get(int x) {
if(par[x] == x) {
return x;
}
return par[x] = get(par[x]);
}
bool same(int a, int b) {
return get(a) == get(b);
}
bool unite(int u, int v) {
if(same(u, v)) {
return false;
}
u = get(u);
v = get(v);
par[u] = v;
return true;
}
};
const double INF = 1E18;
const double EPS = 1E-6;
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) {
DSU dsu(N), dsu2(N);
std::vector<std::pair<int, int>> adj[N];
for(int i = 0; i < M; i++) {
dsu.unite(x[i], y[i]);
if(x[i] != H && y[i] != H) {
dsu2.unite(x[i], y[i]);
}
adj[x[i]].emplace_back(y[i], c[i]);
adj[y[i]].emplace_back(x[i], c[i]);
}
if(!dsu.same(0, H)) {
return -1;
}
K = std::min(80, K);
std::vector<double> pw(K + 1, 1);
for(int i = 1; i <= K; i++) {
pw[i] = pw[i - 1] / 2;
}
using T = std::tuple<double, int, int>;
std::priority_queue<T, std::vector<T>, std::greater<T>> pq;
pq.emplace(0, H, 0);
std::vector dist(N, std::vector<double> (K + 1, -1));
std::vector vis(N, std::vector<bool> (K + 1, false));
double ans = INF;
while(!pq.empty()) {
auto [cost, node, bound] = pq.top();
pq.pop();
if(vis[node][bound]) {
continue;
}
if(arr[node] == 0) {
ans = std::min(ans, cost);
break;
}
dist[node][bound] = cost;
vis[node][bound] = true;
for(auto [child, w] : adj[node]) {
if(dsu2.same(0, child)) {
pq.emplace(cost + w * pw[bound], child, bound);
if(arr[node] == 2 && bound + 1 <= K) {
pq.emplace(cost + w * pw[bound + 1], child, bound + 1);
}
}
}
}
for(int i = 0; i <= K; i++) {
if(vis[0][i]) {
ans = std::min(ans, dist[0][i]);
}
}
if(std::abs(ans - INF) <= EPS) {
return -1;
}
return ans;
}
