// hola soy Dember :D
// 31/03/2024
#include <bits/stdc++.h>
#define ll int
#define pll pair<ll,ll>
#define F first
#define S second
#define Z size()
#define pb push_back
#define bp pop_back
#define fo(x,y,z) for(ll x=y; x<=z; x++)
#define of(x,y,z) for(ll x=y; x>=z; x--)
#define all(n) n.begin(), n.end()
#define arr(x,y,z) x+y, x+y+z
#define dd double
using namespace std;
const dd inf=1e18;
vector<vector<pair<ll, dd>>> v;
vector<dd> dp, tt;
dd ans=1e18;
dd solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
k=min(k, 100);
v.resize(n);
fo(i,0,m-1){
v[x[i]].pb({y[i], c[i]});
v[y[i]].pb({x[i], c[i]});
}
dp.resize(2*n, inf);
//for(auto u:dp)cout<<u<<' ';cout<<"\n";
priority_queue<pair<dd, ll>> q;
fo(j,0,k){
tt.resize(2*n,inf);
if(j){
fo(i,0,n-1){
if(a[i]==1 || dp[i]==inf)continue;
if(a[i]==0)tt[i]=0;
q.push({-dp[i]/2., i});
}
}
else q.push({0., 0});
while(!q.empty()) {
auto [xd, u]=q.top(); xd=-xd;
q.pop();
if(u==h)continue;
for(auto [adios, ola]:v[u]){
if(tt[adios]>xd+ola){
if(a[adios]==0) tt[adios]=0.;
else tt[adios]=xd+ola;
q.push({-tt[adios], adios});
}
}
}
ans=min(ans, tt[h]);
if(j==0 && tt[h]==inf)break;
swap(tt, dp);
}
return ((ans<inf)? ans: -1.);
}
