//*** Bismillah ***//
#pragma GCC optimize("O3", "fast-math", "unroll-loops", "no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
#if !defined(ONLINE_JUDGE) and !defined(EVAL)
#include "template/debug.h"
#else
#define d(x...)
#endif
#define fr first
#define er erase
#define sc second
#define in insert
#define ll int
#define pb push_back
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define len(x)(ll)x.size()
#define all(x)x.begin(),x.end()
const ll INF = 1e9;
const ll INFL = 1e18;
const ll MOD = 1e9+7;
// const ll MOD = 998244353;
const ll maxn = 1e5+5;
#include "cyberland.h"
ll n,m,k=0;
ll d;
vector<pair<ll, double>> g[maxn];
double dis[maxn][66]; // node, nece defe islenib -> min yol
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> a){
n = N, m = M, k = K, d = H + 1;
k = min(k, 65);
for(ll i = 0; i <= n; i ++){
for(ll j = 0; j <= k; j ++){
dis[i][j] = 1e15;
}
g[i].clear();
}
for(ll i = 0; i < m; i ++){
g[x[i] + 1].pb({y[i] + 1, c[i]});
g[y[i] + 1].pb({x[i] + 1, c[i]});
}
priority_queue<pair<double, pll>>q; // w, # of use, u
q.push({0, {0, 1}});
dis[1][0] = 0;
while(!q.empty()){
ll tmpp = q.top().fr, tm = q.top().sc.fr, u = q.top().sc.sc;
q.pop();
if(dis[u][tm] < -tmpp or u == d) continue;
for(auto [v, w] : g[u]){
if(a[u - 1] == 0){
if(dis[v][0] > w){
dis[v][0] = w;
q.push({-dis[v][0], {0, v}});
}
}
else{
if(dis[v][tm] > dis[u][tm] + w){
dis[v][tm] = dis[u][tm] + w;
q.push({-dis[v][tm], {tm, v}});
}
}
if(a[u - 1] == 2 and tm < k){
if(dis[v][tm + 1] > dis[u][tm] / 2 + w){
dis[v][tm + 1] = dis[u][tm] / 2 + w;
q.push({-dis[v][tm + 1], {tm + 1, v}});
}
}
}
}
double cv = 1e15;
for(ll i = 0; i <= k; i ++){
cv = min(cv, dis[d][i]);
d(dis[d][i]);
}
return cv == 1e15 ? -1 : cv;
}
// void _(ll tt){
// }
// signed main(){
// ll tm=clock();
// cin.tie(0)->sync_with_stdio(0);
// ll t=1;
// // cin>>t;
// for(ll tt=1;tt<=t;tt++){
// _(tt);
// }
// cerr<<"\n\033[1;31mTime: \033[1;30m" \
// <<(double)(clock()-tm)/1000000<<"\033[1;32m seconds\n";
// }
