#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
#define ld long double
#define pii pair<ld,int>
#define ll long long
#define rep(i,a,b) for(int i = a; i <= b; i++)
const ll INF = 1e18+10;
const int MAXN = 1e5+10;
bool mk[MAXN];
void dfs(int u, vector<vector<pii>> &g, int H) {
if(mk[u]) return;
mk[u] = 1;
if (u==H) return;
for(auto &[v,w] : g[u]) dfs(v,g);
}
void dijkstra(priority_queue<pii,vector<pii>,greater<pii>> &pq, vector<ld> &dist, vector<vector<pii>> &g, int N) {
vector<bool> vis(N, 0LL);
while (!pq.empty()) {
auto [d,u] = pq.top();pq.pop();
if(vis[u]) continue;
//cout << u << ' ' << d << ' ' << ck << '\n';
vis[u] = 1;
for(auto &[v,w] : g[u]) {
if (d+w >= dist[v]) continue;
dist[v] = d+w;
pq.push({dist[v],v});
}
}
}
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,100);
rep(i,0,N-1) mk[i] = 0;
vector<ld> dist(N, INF);
vector<vector<pii>> g(N);
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);
priority_queue<pii,vector<pii>,greater<pii>> pq;
dist[0] = 0;
pq.push({0,0});
rep(i,1,N-1) if(arr[i]==0 && mk[i]) {
pq.push({0,i});
dist[i] = 0;
}
dijkstra(pq,dist,g,N);
vector<ld> dist2(N,INF);
dist2[H] = 0;
pq.push({0,H});
dijkstra(pq, dist2, g, N);
if(!mk[H]) return -1;
ld ans = INF;
rep(i,0,N-1) {
if(!mk[i]) continue;
int mn = 1e9+10;
for(auto &[v,w] : g[i]) {
if(v!=H) mn = min(mn,w);
}
ld d = dist[i];
if(arr[i] == 2) d /= 2;
rep(j,2,K) {
if(arr[i] != 2) break;
if(d+2*mn >= 2*d) break;
d = d/2+mn;
}
//cout << i << ' ' << dist[i] << ' ' << dist2[i] << '\n';
ans = min(ans, d+dist2[i]);
}
if(ans == INF) return -1;
return ans;
}
