#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
struct edge {
int v;
ld w;
int k;
bool operator< (edge b) const {
if (k != b.k) return k > b.k;
return w > b.w;
}
};
vector<edge> g[100005];
bool vis[100005];
ld di[100005][81];
const ld inf = 1e18;
int h;
void dfs (int u) {
vis[u] = true;
if (u == h) return;
for (auto& [v, w, k] : g[u]) if (!vis[v]) dfs(v);
}
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) {
h = H;
K = min(K, 80);
for (int i = 0; i < N; i++) {
g[i].clear();
vis[i] = false;
for (int j = 0; j <= K; j++) di[i][j] = inf;
}
for (int i = 0; i < M; i++) {
g[x[i]].push_back({y[i], ld(c[i]), 0});
g[y[i]].push_back({x[i], ld(c[i]), 0});
}
dfs(0);
if (!vis[H]) return -1;
priority_queue<edge, vector<edge>> pq;
for (int i = 1; i < N; i++) if (arr[i] == 0 && vis[i]) {
pq.push({i, 0, 0});
di[i][0] = 0;
}
pq.push({0, 0, 0});
di[0][0] = 0;
while (!pq.empty()) {
auto [u, w, k] = pq.top();
pq.pop();
if (u == H) continue;
if (di[u][k] != w) continue;
for (auto& [v, vw, vk] : g[u]) if (arr[v] != 0) {
if (arr[v] == 2 && k+1 <= K && di[v][k+1] > (w+vw)/2) {
di[v][k+1] = (w+vw)/2;
pq.push({v, (w+vw)/2, k+1});
}
if (di[v][k] > w+vw) {
di[v][k] = w+vw;
pq.push({v, w+vw, k});
}
}
}
ld ans = inf;
for (int i = 0; i <= K; i++) ans = min(ans, di[H][i]);
return ans == inf ? -1 : ans;
}
