#include <bits/stdc++.h>
using namespace std;
const int N=100000;
vector<pair<int,double>> edges[N];
bool visited[N]={};
double ans[61][N];
void dfs(int u,int h){
for(auto v:edges[u]){
if(v.first==h) continue;
if(!visited[v.first]){
visited[v.first]=true;
dfs(v.first, h);
}
}
}
double solve(int n,int m,int k,int h,vector<int> x,vector<int> y,vector<int> c,vector<int> a){
k=min(k,60);
for(int j=0;j<=k;j++)for(int i=0;i<n;i++) ans[j][i]=-1;
for(int i=0;i<m;i++){
edges[x[i]].push_back(make_pair(y[i],(double) c[i]));
edges[y[i]].push_back(make_pair(x[i],(double) c[i]));
}
priority_queue<pair<double,pair<int,int>>,vector<pair<double,pair<int,int>>>,greater<pair<double,pair<int,int>>>> pq;
ans[0][0]=0;
visited[0]=true;
dfs(0,h);
pq.push(make_pair(0,make_pair(0,0)));
for(int i=0;i<n;i++){
if(a[i]==0 && visited[i]){
ans[0][i]=0;
pq.push(make_pair(0,make_pair(0,i)));
}
}
while(!pq.empty()){
auto u=pq.top();
pq.pop();
if(u.second.second==h) continue;
if(u.first!=ans[u.second.first][u.second.second]) continue;
for(auto v:edges[u.second.second]){
if(ans[u.second.first][v.first]==-1 || ans[u.second.first][v.first]>u.first+v.second){
ans[u.second.first][v.first]=u.first+v.second;
pq.push(make_pair(ans[u.second.first][v.first],make_pair(u.second.first,v.first)));
}
if(a[v.first]==2 && u.second.first<k){
if(ans[u.second.first+1][v.first]==-1 || ans[u.second.first+1][v.first]>(u.first+v.second)/((double) 2)){
ans[u.second.first+1][v.first]=(u.first+v.second)/((double) 2);
pq.push(make_pair(ans[u.second.first+1][v.first],make_pair(u.second.first+1,v.first)));
}
}
}
}
double fans=-1;
for(int j=0;j<=k;j++){
if(ans[j][h]==-1) continue;
if(fans==-1 || fans>ans[j][h]) fans=ans[j][h];
}
for(int i=0;i<n;i++){
edges[i].clear();
visited[i]=false;
}
for(int j=0;j<=k;j++) for(int i=0;i<n;i++) ans[j][i]=0;
return fans;
}
