#include "cyberland.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> adj[100100];
bool visited[100100];
void dfs(int cur, int H){
visited[cur]=true;
for(int i=0; i<(int)adj[cur].size(); i++){
int viz=adj[cur][i].first;
int w=adj[cur][i].second;
if(viz==H){
adj[H].push_back({cur, w});
continue;
}
if(visited[viz])continue;
dfs(viz, H);
}
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int>
y, vector<int> c, vector<int> arr){
for(int i=0; i<N; i++){
visited[i]=0;
adj[i].clear();
}
for(int i=0; i<M; i++){
if(x[i]!=H)adj[x[i]].push_back({y[i], c[i]});
if(y[i]!=H)adj[y[i]].push_back({x[i], c[i]});
}
K=min(K, 70);
dfs(0, H);
long double dist[100100][75], po[74];
bool achou[100100][75];
po[0]=1;
for(int i=1; i<=K; i++)po[i]=po[i-1]*2;
for(int i=0; i<N; i++){
for(int j=0; j<=K; j++){
dist[i][j]=1e15;
achou[i][j]=0;
}
}
priority_queue<pair<long double, pair<int, int>>, vector<pair<long double, pair<int,int>>>, greater<pair<long double, pair<int,int>>>> pq;
pq.push({0, {H, 0}});
dist[H][0]=0;
while(!pq.empty()){
pair<long double, pair<int,int>> curtop=pq.top();
pq.pop();
int cur=curtop.second.first;
int curk=curtop.second.second;
if(cur==0 || arr[cur]==0 || curk==K){
return dist[cur][curk];
}
if(achou[cur][curk])continue;
achou[cur][curk]=true;
for(int i=0; i<(int)adj[cur].size(); i++){
int viz=adj[cur][i].first;
if(viz==H)continue;
long double w=adj[cur][i].second;
if(arr[cur]==2){
w/=po[curk+1];
if(dist[viz][curk+1]>dist[cur][curk]+w){
dist[viz][curk+1]=dist[cur][curk]+w;
pq.push({dist[viz][curk+1], {viz, curk+1}});
}
}
else if(dist[viz][curk]>dist[cur][curk]+w/po[curk]){
w/=po[curk];
dist[viz][curk]=dist[cur][curk]+w;
pq.push({dist[viz][curk], {viz, curk}});
}
}
}
return -1;
}
