#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
const double inf = 1e18;
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, 66);
vector<pair<int, double>> adj[N + 1];
for(int i = 0; i < M; ++i){
adj[x[i]].push_back({y[i], (double) c[i] * 1.00});
adj[y[i]].push_back({x[i], (double) c[i] * 1.00});
}
vector<vector<double>> dp(N + 1, vector<double>(K + 1, inf));
priority_queue<tuple<double,int,int>> pq;
dp[0][K] = 0;
pq.push({0.0, 0, -K});
while(!pq.empty()){
auto [dist, node, rem] = pq.top(); dist = -dist, rem = -rem;
pq.pop();
if(dist > dp[node][rem]) continue;
if(node == H) continue;
double base = dist;
if(arr[node] == 0) base = 0;
for(auto [v, w] : adj[node]){
if(dp[v][rem] > base + w){
dp[v][rem] = base + w;
pq.push({-dp[v][rem], v, -rem});
}
if(arr[node] == 2 && rem > 0){
if(dp[v][rem-1] > base / 2 + w){
dp[v][rem-1] = base / 2 + w;
pq.push({-dp[v][rem-1], v, 1 - rem});
}
}
}
}
double ans = inf;
for(int i = 0; i <= K; ++i) ans = min(ans, dp[H][i]);
return ((ans >= inf || ans <= 0) ? -1 : ans);
}
