#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'
#include "cyberland.h"
#include <vector>
vector<pair<int,int>> adj[100001];
long double dist[100001][101];
bool vis[100001][101];
double solve(int n, int m, int k, int x,vector<int> aa,vector<int> bb, vector<int> cc, vector<int> it) {
for(int i=0;i<n;i++){
adj[i].clear();
for(int j=0;j<=min(70,k);j++){
dist[i][j]=-1;
vis[i][j]=0;
}
}
for(int i=0;i<m;i++){
adj[aa[i]].pb({bb[i],cc[i]});
adj[bb[i]].pb({aa[i],cc[i]});
}
dist[0][0]=0;
vis[0][0]=1;
/*
priority_queue<pair<long double,pair<int,int>>> ss;
ss.push({0,{0,0}});*/
for(int i=0;i<=min(70,k);i++){
priority_queue<pair<long double,pair<int,int>>> ss;
for(int j=0;j<n;j++){
if(vis[j][i]==1 and j!=x){
ss.push({-dist[j][i],{j,i}});
}
}
while(ss.size()){
pair<long double,pair<int,int>> no=ss.top();
no.a=-no.a;
ss.pop();
if(dist[no.b.a][no.b.b]<no.a){
continue;
}
if(no.b.a==x){
continue;
}
for(auto j:adj[no.b.a]){
long double mi=no.a+j.b;
pair<int,int> rr={j.a,no.b.b};
if(it[j.a]==0){
mi=0;
}
if(vis[rr.a][rr.b]==0 or dist[rr.a][rr.b]>=mi+0.000000001){
dist[rr.a][rr.b]=mi;
vis[rr.a][rr.b]=1;
ss.push({-mi,{rr.a,rr.b}});
}
if(it[j.a]==2){
mi/=(long double)2;
rr.b+=1;
if(rr.b>70){
continue;
}
if(vis[rr.a][rr.b]==0 or dist[rr.a][rr.b]>=mi+0.000000001){
dist[rr.a][rr.b]=mi;
vis[rr.a][rr.b]=1;
//ss.push({-mi,{rr.a,rr.b}});
}
}
}
}
}
long double ans=-1;
int st=0;
for(int i=0;i<=min(k,70);i++){
if(vis[x][i]==1){
if(st==0){
st=1;
ans=dist[x][i];
}
if(dist[x][i]<=ans-0.0000001){
ans=dist[x][i];
}
}
}
return ans;
}
