#include<bits/stdc++.h>
#define pb push_back
#define lint long long int
using namespace std;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> abi) {
vector<vector<pair<int, double>>> edge(n);
for (int i = 0; i < m; i ++) {
edge[x[i]].pb({y[i], c[i]});
edge[y[i]].pb({x[i], c[i]});
}
double ans;
vector<int> visited(n, 0);
priority_queue<tuple<double, int, int>> pq;
pq.push(make_tuple(0, 0, 0)); // -w, v, k
visited[0] ++;
while (!pq.empty()) {
tuple<double, int, int> cur = pq.top(); pq.pop();
double w = get<0>(cur); w *= -1;
int v = get<1>(cur), k = get<2>(cur);
if (v == n-1) {
ans = w;
break;
}
for (auto [cv, cw] : edge[v]) {
if (visited[cv] == 2) {continue;}
visited[cv] ++;
if (abi[cv] == 0) {
pq.push({make_tuple(0, cv, k)});
}
else if (abi[cv] == 2) {
if (k > 0) pq.push({make_tuple(-(w+cw)/2, cv, k-1)});
pq.push({make_tuple(-(w+cw), cv, k)});
}
else {
pq.push({make_tuple(-(w+cw), cv, k)});
}
}
}
return ans;
}
