#include "cyberland.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int NN = 1e5 + 10;
vector<pair<int, double>> adj[NN];
double dp[NN][76];
long long dist[NN];
bool marked[NN];
bool reachable[NN];
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, 75);
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 <= K; j++){
dp[i][j] = numeric_limits<double>::max();
}
reachable[i] = 0;
marked[i] = 0;
}
queue<int> q;
q.push(0);
marked[0] = 1;
while(!q.empty()){
auto node = q.front();
q.pop();
for(auto [u, w] : adj[node]){
if(marked[u] || u == H) continue;
marked[u] = 1;
q.push(u);
if(arr[u] == 0) reachable[u] = 1;
}
}
priority_queue<pair<double, pair<int,int>>, vector<pair<double, pair<int,int>>>, greater<pair<double, pair<int,int>>>> pq;
pq.push({0, {0, 0}});
for(int i = 0; i < N; i++){
if(reachable[i]){
pq.push({0, {0, i}});
dp[i][0] = 0;
}
}
dp[0][0] = 0;
while(!pq.empty()){
auto[D, meronq] = pq.top();
auto [k, node] = meronq;
pq.pop();
if(D != dp[node][k] || node == H) continue;
for(auto [u, w] : adj[node]){
if(arr[u] == 0) continue;
if(dp[u][k] > dp[node][k] + w){
dp[u][k] = dp[node][k] + w;
pq.push({dp[u][k], {k, u}});
}
if(arr[u] == 2){
if(k + 1 <= K && dp[u][k + 1] > (double)(dp[node][k] + w) / (double)2.0){
dp[u][k + 1] = (double)(dp[node][k] + w) / (double)2.0;
pq.push({dp[u][k + 1], {k + 1, u}});
}
}
}
}
// for(int i = 0; i < N; i++){
// for(int j = 0; j <= K; j++){
// cerr << "dp[" << i << "][" << j << "] = " << dp[i][j] << endl;
// }
// }
double ans = numeric_limits<double>::max();
for(int i = 0; i <= K; i++){
ans = min(ans, dp[H][i]);
}
for(int i = 0; i < N; i++){
adj[i].clear();
}
return (ans == 1e18 ? -1 : ans);
}
