#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define tp3 tuple<ld, int, int>
const int N = 1e5+5, K = 51;
const ld D = 2, INF = LLONG_MAX;
int n, h, k;
ld mn[N], dis[2][K][N];
vector<int> arr;
vector<pair<int, ld>> adj[N];
void dijkstra(int x, int idx) {
priority_queue<tp3> pq;
if (idx == 1) {
for (int i = 0; i < n; i++) {
if (arr[i] || dis[0][0][i] == INF) continue;
pq.push(make_tuple(-0, 0, i));
}
}
else {
pq.push(make_tuple(-0, 0, x));
}
while (!pq.empty()) {
ld d = -get<0>(pq.top());
int divs = get<1>(pq.top());
int y = get<2>(pq.top());
pq.pop();
if (dis[idx][divs][y] <= d) continue;
dis[idx][divs][y] = d;
if (y == h) continue;
if (arr[y] == 2 && divs+1 < min(k, K) && dis[idx][divs+1][y] > ((d+mn[y]) / D)) {
pq.push(make_tuple(-((d+mn[y]) / D), divs+1, y));
}
for (auto& [z, d2] : adj[y]) {
if (dis[idx][divs][z] > (d+d2)) {
pq.push(make_tuple(-(d+d2), divs, z));
}
if (arr[z] == 2 && divs+1 < min(k, K) && dis[idx][divs+1][z] > ((d+d2) / D)) {
pq.push(make_tuple(-((d+d2) / D), divs+1, z));
}
}
}
}
double solve(int N, int m, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> ARR) {
n = N;
h = H;
k = K;
arr = ARR;
for (int i = 0; i < n; i++) {
adj[i].clear();
}
for (int i = 0; i < m; i++) {
adj[x[i]].push_back(make_pair(y[i], c[i]));
adj[y[i]].push_back(make_pair(x[i], c[i]));
}
for (int i = 0; i < n; i++) {
mn[i] = INF;
for (auto& [j, d] : adj[i]) {
if (j == h) continue;
mn[i] = min(mn[i], d);
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < K; j++) {
for (int k = 0; k < n; k++) {
dis[i][j][k] = INF;
}
}
}
dijkstra(0, 0);
dijkstra(0, 1);
ld ans = INF;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < min(K, k+1); j++) {
ans = min(ans, dis[i][j][h]);
}
}
return (ans == INF ? (ld)(-1) : ans);
}
