#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define double long double
const ll NMAX = 1e5 + 5;
vector<pair<ll,ll> > g[NMAX];
vector<vector<double> > dis(NMAX, vector<double>(31) );
double solve(int n, int m, int k, int h, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
for(long long i = 1; i <= n; i++){
g[i].clear();
for(long long j = 0; j <= 30; j++) dis[i][j] = 1e18;
}
h++;
for(long long i = 0; i < m; i++){
g[x[i] + 1].push_back({y[i] + 1, c[i]});
g[y[i] + 1].push_back({x[i] + 1, c[i]});
}
priority_queue<tuple<double,long long,long long>, vector<tuple<double,long long,long long> >, greater<tuple<double,long long,long long> > > q;
q.push({0, 1, 0});
dis[1][0] = 0;
while(!q.empty()){
auto [dist, v, u] = q.top();
q.pop();
if(dist > dis[v][u]) continue;
for(auto [to, cost] : g[v]){
if(arr[to - 1] == 2 and u < 30 and (dist + cost) / 2 < dis[to][u + 1]){
dis[to][u + 1] = ((double)dist + cost) / 2.0;
q.push({dis[to][u + 1], to, u + 1});
}
if(arr[to - 1] == 0 and dis[to][u] > 0){
dis[to][u] = 0;
q.push({dis[to][u], to, u});
}
if(dist + cost < dis[to][u]){
dis[to][u] = dist + cost;
q.push({dis[to][u], to, u});
}
}
}
double ans = 1e18;
for(long long i = 0; i <= k; i++) ans = min(ans, dis[h][i]);
return ans;
}
