// 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;
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]});
}
vector<double> dp(n), tt(n);
for(auto &p:dp) p=inf;
for(auto &p:tt) p=inf;
priority_queue<pair<dd, ll>> q;
tt[0]=0.;
fo(j,0,k){
vector<double> tt(n); for(double &p:tt) p=inf;
if(j){
for(int i=0; i<n; i++){
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 [cur, u]=q.top(); cur=-cur;
q.pop();
if(u==h) continue;
for(auto [v, w]:v[u]) {
if(tt[v]>cur+w) {
if(a[v]==0) tt[v]=0.;
else tt[v]=cur+w;
q.push({-tt[v], v});
}
}
}
ans=min(ans, tt[h]);
if(j==0 && tt[h]==inf) break;
swap(tt, dp);
}
return ((ans<inf)? ans: -1.);
}
