#include "cyberland.h"
#include <bits/stdc++.h>
#define ll long double
using namespace std;
const int nx = 1e5 + 5, kx = 68;
const ll INF = 4e18;
bool vis[nx];
ll dist[nx][kx];
vector<pair<int, ll>> adj[nx];
priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq;
queue<int> q;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
K = min(K, 67);
while(!pq.empty()) pq.pop();
while(!q.empty()) q.pop();
for(int i = 0;i<N;i++){
adj[i].clear();
vis[i] = 0;
for(int j = 0;j<=K;j++) dist[i][j] = INF;
}
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]});
for(int i = 0;i<N;i++) for(int j = 0;j<kx;j++) dist[i][j] = INF;
q.push(0);
vis[0] = 1;
while(!q.empty()){
int u = q.front();
q.pop();
if(u == H) continue;
for(auto [v, w] : adj[u]){
if(!vis[v]){
vis[v] = 1;
q.push(v);
}
}
}
if(!vis[H]) return -1;
dist[0][0] = 0;
pq.push({0, 0, 0});
for(int i = 1;i<N;i++){
if(vis[i] && arr[i] == 0){
dist[i][0] = 0;
pq.push({0, 0, i});
}
}
ll mn = INF;
while(!pq.empty()){
auto [d, k, u] = pq.top();
pq.pop();
if(d > dist[u][k] || u == H) continue;
for(auto [v, w] : adj[u]){
if(d + w < dist[v][k]){
dist[v][k] = d + w;
pq.push({d + w, k, v});
}
if(arr[v] == 2 && k < K){
if((d + w) / 2.0L < dist[v][k + 1]){
dist[v][k + 1] = (d + w) / 2.0L;
pq.push({dist[v][k + 1], k + 1, v});
}
}
}
}
for(int i = 0;i<=K;i++) mn = min(mn, dist[H][i]);
}
