#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
int h2;
vector<bool> vab(1e5), vab2(1e5);
vector<vector<bool>> vis(1e5, vector<bool> (56)), vis2(1e5, vector<bool> (56));
vector<vector<pair<int, double>>> adj(1e5);
vector<vector<double>> dist(1e5, vector<double> (56, 1e18)), dist2(1e5, vector<double> (56, 1e18));
void dfs(int u){
vab[u] = 1;
for (auto z: adj[u]){
if (!vab[z.first]) dfs(z.first);
}
}
void dfs2(int u){
vab2[u] = 1;
for (auto z: adj[u]){
if (z.first != h2 && !vab2[z.first]) dfs2(z.first);
}
}
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
h2 = h;
if (k > 55) k = 55;
for (int i = 0; i < n; i++){
vab[i] = 0;
vab2[i] = 0;
adj[i].clear();
for (int j = 0; j <= k; j++){
vis[i][j] = 0;
vis2[i][j] = 0;
dist[i][j] = 1e18;
dist2[i][j] = 1e18;
}
}
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]});
}
dfs(0);
dfs2(0);
if (vab[h] == 0) return -1;
priority_queue<pair<pair<int, double>, pair<int, bool>>, vector<pair<pair<int, double>, pair<int, bool>>>, greater<pair<pair<int, double>, pair<int, bool>>>> pq;
pq.push({{0, 0}, {0, 1}});
for (int i = 1; i < n; i++){
if (arr[i] == 0 && vab2[i] == 1) pq.push({{0, 0}, {i, 0}});
}
while (pq.size()){
double d = pq.top().first.second;
bool b = pq.top().second.second;
int in = pq.top().second.first, l = pq.top().first.first;
pq.pop();
if (b == 1){
if (vis2[in][l]) continue;
vis2[in][l] = 1;
dist2[in][l] = d;
}
else{
if (vis[in][l]) continue;
vis[in][l] = 1;
dist[in][l] = d;
}
if (in == h) continue;
for (auto z: adj[in]){
pq.push({{l, d + z.second}, {z.first, 0}});
}
if (arr[in] != 2 || b) continue;
if (l < k) pq.push({{l + 1, d / 2}, {in, 1}});
}
double ans = 1e18;
for (int i = 0; i <= k; i++){
ans = min(ans, dist[h][i]);
}
return ans;
}
