#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define node tuple<int, double, int>
const double inf = 1e15;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
vector<pii> g[n + 1];
for (int i = 0; i < m; i++){
x[i]++; y[i]++;
g[x[i]].pb({y[i], c[i]});
g[y[i]].pb({x[i], c[i]});
}
k = min(k, 69); // LOL
arr.insert(arr.begin(), 0); h++;
vector<bool> used(n + 1); used[1] = 1;
queue<int> q; q.push(1);
while (!q.empty()){
int v = q.front(); q.pop();
if (v == h) continue;
for (auto [u, w]: g[v]){
if (!used[u]){
used[u] = 1;
q.push(u);
}
}
}
double dp[n + 1][k + 1];
for (int i = 1; i <= n; i++){
for (int j = 0; j <= k; j++){
dp[i][j] = inf;
}
}
priority_queue<node, vector<node>, greater<node>> pq;
dp[1][0] = 0; pq.push({0, 0, 1});
for (int i = 1; i <= n; i++){
if (used[i] && !arr[i]){
for (int j = 0; j <= k; j++){
dp[i][j] = 0;
}
pq.push({0, 0, i});
}
}
while (!pq.empty()){
node f = pq.top(); pq.pop();
auto [x, d, v] = f;
if (v == h) continue;
for (auto [u, w]: g[v]){
if (arr[u] == 1){
double dist = d + w;
if (dist < dp[u][x]){
dp[u][x] = dist;
pq.push({x, dist, u});
}
}
else if (arr[u] == 2){
double dist = d + w;
if (dist < dp[u][x]){
dp[u][x] = dist;
pq.push({x, dist, u});
}
dist /= 2;
if (x < k && dist < dp[u][x + 1]){
dp[u][x + 1] = dist;
pq.push({x + 1, dist, u});
}
}
}
}
double out = inf;
for (int i = 0; i <= k; i++){
out = min(out, dp[h][i]);
}
return (out == inf) ? -1 : out;
}
