#include "cyberland.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
typedef long double ld;
const long double inf = 1e18;
vector<vector<pair<int, long double>>> graph;
vector<bool> reachable;
void dfs(int nd){
if(reachable[nd]) return;
reachable[nd] = 1;
for(auto [x, w]: graph[nd]) dfs(x);
}
double solve(int n, int m, int k, int h, vector<int> U, vector<int> V, vector<int> C, vector<int> arr){
k = min(k, 70);
k++;
graph.assign(n, {});
vector<pair<int, long double>> edge_with_h;
reachable.assign(n, 0);
for(int i = 0; i < m; i++){
if(U[i] == h || V[i] == h){
edge_with_h.pb({U[i]+V[i]-h, C[i]});
continue;
}
graph[U[i]].pb({V[i], C[i]});
graph[V[i]].pb({U[i], C[i]});
}
dfs(0);
vector<long double> dis(n, inf);
vector<bool> bl(n, 0);
priority_queue
<pair<long double, int>, vector<pair<long double, int>>, greater<pair<long double, int>>> pq;
for(int i = 0; i < n; i++) if(i == 0 || (arr[i] == 0 && reachable[i])){
dis[i] = 0;
}
for(int ki = 0; ki < k; ki++){
if(ki != 0){
auto _dis = dis;
for(int i = 0; i < n; i++) if(arr[i] == 2 && reachable[i]){
if(i == h) continue;
for(auto [x, w]: graph[i]) dis[i] = min(dis[i], (_dis[x]+w)/ld(2));
}
}
bl.assign(n, 0);
for(int i = 0; i < n; i++) if(reachable[i]) pq.push({dis[i], i});
while(!pq.empty()){
int nd = pq.top().sc;
pq.pop();
if(bl[nd]) continue;
bl[nd] = 1;
for(auto [x, w]: graph[nd]) if(dis[nd]+w < dis[x]){
dis[x] = dis[nd]+w;
pq.push({dis[x], x});
}
}
}
long double ans = inf;
for(auto [x, w]: edge_with_h){
ans = min(ans, dis[x]+w);
}
if(ans >= inf) return -1;
return ans;
}
