#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
using ld = long double; using vi = vector<int>;
const ld INF = 1e18;
double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) {
ld tmin[N][K+1];
for (ll i=0;i<N;i++) {
for (ll k=0;k<=K;k++) {
tmin[i][k]=INF;
}
}
vector<pii> adj[N]; //vertex,cost
for (ll i=0;i<M;i++) {
adj[x[i]].push_back({y[i],c[i]});
adj[y[i]].push_back({x[i],c[i]});
}
priority_queue<pair<ld,pii>> pq; //{time,{position, #k}}
pq.push({0.0,{0,0}});
while (!pq.empty()) {
auto A = pq.top(); pq.pop();
ld T = A.first; ll x = A.second.first; ll k = A.second.second;
if (arr[x]==0) {
T = 0.0; k = 0;
}
if (tmin[x][k]<=T) {
continue;
}
tmin[x][k]=min(tmin[x][k],T);
if (x==H) {
continue;
}
for (pii p0: adj[x]) {
ll y = p0.first; ld ce = p0.second;
pq.push({ce+T,{y,k}});
if (arr[x]==2 && k<K) {
pq.push({ce+T/2,{y,k+1}});
}
}
}
ld ans = INF;
for (ll k=0;k<=K;k++) {
ans = min(ans,tmin[H][k]);
}
if (ans == INF) {
return -1.0;
} else {
return ans;
}
}
