/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#include "cyberland.h"
using ld=long double;
const ld eps=1e-10;
struct tp{
ld v;
tp(ld vl=0){v=vl;}
};
bool operator>(const tp&a,const tp&b){
return (a.v-b.v>eps);
}
bool operator<(const tp&a,const tp&b){
return (b>a);
}
bool operator==(const tp&a,const tp&b){
return (abs(a.v-b.v)<eps);
}
bool operator<=(const tp&a,const tp&b){
return (a<b)||(a==b);
}
bool operator>=(const tp&a,const tp&b){
return (a>b)||(a==b);
}
double solve(int n,int m,int k,int h,vector<int>x,vector<int>y,vector<int>c,vector<int>arr){
vector<vector<array<int,2>>>a(n);
while(m--){
int u=x[m],v=y[m],w=c[m];
a[u].push_back({v,w});
a[v].push_back({u,w});
}
priority_queue<pair<tp,pair<int,int>>,vector<pair<tp,pair<int,int>>>,greater<pair<tp,pair<int,int>>>>q;
vector<vector<tp>>d(n,vector<tp>(k+1));
for(auto&i:d)for(auto&j:i)j.v=1e18;
cout<<fixed<<setprecision(6);
q.push({tp(),{k,0}});
d[0][k]=0;
while(!q.empty()){
tp w=q.top().first;
int i=q.top().second.second;
int kk=q.top().second.first;
q.pop();
if(d[i][kk]<w||i==h)continue;
for(auto&[j,ww]:a[i]){
if(arr[j]==0){
if(d[j][kk].v>eps){
d[j][kk].v=0;
q.push({tp(),{kk,j}});
}
}
if(arr[j]==2&&kk>0){
if(d[j][kk-1].v-((ww+w.v)/2.000000000)>eps){
d[j][kk-1].v=(ww+w.v)/2.000000000;
q.push({d[j][kk-1],{kk-1,j}});
}
}
if(d[j][kk].v>(ww+w.v)>eps){
d[j][kk].v=ww+w.v;
q.push({d[j][kk],{kk,j}});
}
}
}
ld ans=1e18;
for(auto&i:d[h])ans=min(ans,i.v);
return (abs(ans-1e18)<eps?-1:ans);
}
//signed main(){
// ios_base::sync_with_stdio(0);cin.tie(0);
//
//
// ;
//
//
// return 0;
//}
