#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
const int N = 1e5 + 5;
double dist[62][N];
priority_queue<pair<double, ii>, vector<pair<double, ii>>, greater<pair<double, ii>>> Q;
vector<ii> G[N];
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, 60);
FOR (i, 0, N-1) FOR (j, 0, K) dist[j][i] = 1e18;
dist[0][0] = 0;
FOR (i, 0, M-1){
G[x[i]].pb({y[i], c[i]});
G[y[i]].pb({x[i], c[i]});
}
vi vis(N, 0);
queue<int> q; q.push(0);
vis[0] = 1;
Q.push({0, {0, 0}});
while (!q.empty()){
int u = q.front(); q.pop();
if (u == H) continue;
for (ii &v : G[u]){
if (vis[v.fi]) continue;
if (arr[v.fi] == 0) Q.push({dist[0][v.fi] = 0, {v.fi, 0}});
vis[v.fi] = 1;
q.push(v.fi);
}
}
double ans = 1e18;
while (!Q.empty()){
double w = Q.top().fi;
int u = Q.top().se.fi, k = Q.top().se.se; Q.pop();
if (u == H) {
ans = min(ans, w);
continue;
}
if (w != dist[k][u]) continue;
for(ii &v : G[u]){
double c = v.se;
if (dist[k][v.fi] > w + c){
Q.push({dist[k][v.fi] = w + c, {v.fi, k}});
}
if (k < K && arr[v.fi] == 2 && dist[k+1][v.fi] > (w + c)/2.0){
Q.push({dist[k+1][v.fi] = (w + c)/2.0, {v.fi, k + 1}});
}
}
}
FOR (i, 0, N-1) G[i].clear();
return (ans >= 1e18 ? -1 : ans);
}
