#include <bits/stdc++.h>
using namespace std;
#include "cyberland.h"
typedef long double ld;
typedef long long ll;
#define fi first
#define se second
#define pi pair<int, int>
#define pii pair<int, pi>
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector <pi> adj[100000];
double dist[69][100000];
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) {
K = min(K, 68);
priority_queue <pair<double, pi>, vector<pair<double, pi> >, greater<pair<double, pi> > > pq;
pq.push({0.0, {0, 0}});
for(int i=0;i<N;i++)for(int j=0;j<=K;j++)dist[j][i] = 1e18;
dist[0][0] = 0;
for(int i=0;i<N;i++)adj[i].clear();
for(int i=0;i<M;i++){
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
while(!pq.empty()){
double a = pq.top().fi; int b = pq.top().se.fi, c = pq.top().se.se;
pq.pop();
if(dist[c][b] < a || b == H)continue;
for(auto [i, j] : adj[b]){
if(arr[i] == 0){
if(dist[c][i])dist[c][i] = 0, pq.push({0, {i, c}});
}
else if(dist[c][i] > a + j)dist[c][i] = a + j, pq.push({dist[c][i], {i, c}});
if(arr[i] == 2 && c < K){
if(dist[c+1][i] > (a + ((double)j)) / 2)dist[c+1][i] = (a + ((double)j)) / 2, pq.push({dist[c+1][i], {i, c+1}});
}
}
}
double ans = 1e18;
for(int i=0;i<=K;i++)ans = min(ans, dist[i][H]);
if(ans > 1e15)return -1;
else return ans;
}
