#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef tuple<db,int,int,bool> t4;
const int N=1e5+5;
const int K=75;
int n,m,k,h;
int a[N];
db dp[N][K][2];
bool vis[N][K][2];
vector<pair<int,db>> adj[N];
priority_queue<t4,vector<t4>,greater<t4>> pq;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
n=N,m=M,k=min(K,70),h=H;
for(int i=0;i<n;i++)adj[i].clear();
for(int i=0;i<m;i++){
int u=x[i],v=y[i],w=c[i];
adj[u].emplace_back(v,w);
adj[v].emplace_back(u,w);
}
for(int i=0;i<n;i++)a[i]=arr[i];
for(int i=0;i<n;i++){
for(int j=0;j<=k;j++){
dp[i][j][0]=dp[i][j][1]=DBL_MAX;
vis[i][j][0]=vis[i][j][1]=false;
}
}
while(!pq.empty())pq.pop();
pq.emplace(0,h,0,0);
for(int i=0;i<=k;i++)dp[h][i][0]=dp[h][i][1]=0;
while(!pq.empty()){
auto [d,u,s,f]=pq.top();
pq.pop();
if(vis[u][s][f])continue;
vis[u][s][f]=true;
for(auto [v,w]:adj[u]){
db res=d+(f?0:w/pow(2.0,s));
if(res>=dp[v][s][f])continue;
dp[v][s][f]=res;
pq.emplace(res,v,s,f);
}
if(a[u]==0&&f==0){
for(auto [v,w]:adj[u]){
db res=d;
if(res>=dp[v][s][1])continue;
dp[v][s][1]=res;
pq.emplace(res,v,s,1);
}
}
if(a[u]==2&&s<k){
for(auto [v,w]:adj[u]){
db res=d+(f?0:w/pow(2.0,s+1));
if(res>=dp[v][s+1][f])continue;
dp[v][s+1][f]=res;
pq.emplace(res,v,s+1,f);
}
}
}
db ans=DBL_MAX;
for(int i=0;i<=k;i++)ans=min({ans,dp[0][i][0],dp[0][i][1]});
if(ans==DBL_MAX)ans=-1;
return ans;
}
