#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using dii=tuple<double,int,int>;
double dist[101010][71],p[71];
int pr[101010];
vector<pair<int,double>> adj[101010];
priority_queue<dii,vector<dii>,greater<dii>> pq;
int find_(int n) {
if(n==pr[n]) return n;
return pr[n]=find_(pr[n]);
}
void uni(int x,int y) {
pr[find_(x)]=find_(y);
}
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) {
while(!pq.empty()) pq.pop();
for(int i=0;i<N;i++) adj[i].clear();
K=min(K,70);
p[0]=1;
for(int i=1;i<=K;i++) p[i]=p[i-1]*0.5;
for(int i=0;i<N;i++) pr[i]=i;
for(int i=0;i<M;i++) {
if(x[i]!=H&&y[i]!=H) uni(x[i],y[i]);
adj[x[i]].eb(make_pair(y[i],c[i])); adj[y[i]].eb(make_pair(x[i],c[i]));
}
for(int i=0;i<N;i++) for(int j=0;j<=K;j++) dist[i][j]=1e18;
for(int i=0;i<=K;i++) dist[H][i]=0;
arr[0]=0;
pq.push(dii(0,H,0));
while(!pq.empty()) {
auto [d,cur,k]=pq.top(); pq.pop();
if(d>dist[cur][k]) continue;
if(arr[cur]==0) return d;
for(auto [i,c]:adj[cur]) {
if(find_(i)!=find_(0)) continue;
if(dist[i][k]>d+c*p[k]) {
dist[i][k]=d+c*p[k];
pq.push(dii(dist[i][k],i,k));
}
if(arr[i]==2&&k+1<=K && dist[i][k+1]>d+c*p[k]) {
dist[i][k+1]=d+c*p[k];
pq.push(dii(dist[i][k+1],i,k+1));
}
}
}
return -1;
}
