// hola soy Dember :D
// 31/03/2024
#include <bits/stdc++.h>
#define dd double
using namespace std;
const dd inf=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);
vector<vector<pair<int, dd>>> v(n);
for(int i=0; i<m; i++){
v[x[i]].push_back({y[i], c[i]});
v[y[i]].push_back({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, int>> q;
tt[0]=0.;
dd ans=1e18;
for(int j=0; j<=k; j++){
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.);
}
