#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vint = vector<int>;
using vll = vector<ll>;
using pint = pair<int, int>;
using vpint = vector<pint>;
using vdouble = vector<double>;
using vbool = vector<bool>;
using tdii = tuple<double, int, int>;
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1, i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a)-1, i >= (b); i--)
#define fi first
#define se second
#define pb push_back
const int K_MAX = 80;
double solve(int N, int M, int K, int H, vint X, vint Y, vint C, vint A) {
K = min(K, K_MAX);
vint type0; type0.push_back(0);
vector<vpint> adj(N);
rep(i, M) adj[X[i]].pb({Y[i], C[i]}), adj[Y[i]].pb({X[i], C[i]});
{
vint st; st.push_back(0);
vbool visited(N);
while (!st.empty()) {
int val = st.back(); st.pop_back();
visited[val] = true;
if (A[val] == 0) type0.pb(val);
for (auto& [ot, cost]: adj[val]) if (!visited[ot] && ot != H) {
st.pb(ot);
}
}
}
vdouble dist[K_MAX+1];
fill(all(dist), vdouble(N, INFINITY));
priority_queue<tdii, vector<tdii>, greater<>> pq;
for (auto& i: type0) pq.push({0, 0, i}), dist[0][i] = 0;
while (!pq.empty()) {
auto [dv, kv, tp] = pq.top(); pq.pop();
if (tp == H || dist[kv][tp] < dv) continue;
for (auto& [ed, cst]: adj[tp]) {
if (dist[kv][tp] + cst < dist[kv][ed]) {
dist[kv][ed] = dist[kv][tp] + cst;
pq.push({dist[kv][ed], kv, ed});
}
}
for (auto& [ed, cst]: adj[tp]) {
if (A[ed] == 2 && kv+1 <= K)
if ((dist[kv][tp] + cst)/2 < dist[kv+1][ed]) {
dist[kv+1][ed] = (dist[kv][tp] + cst)/2;
pq.push({dist[kv+1][ed], kv+1, ed});
}
}
}
double res = INFINITY;
rep(i, K+1) res = min(res, dist[i][H]);
if (res == INFINITY) return -1;
return res;
}
