#include <bits/stdc++.h>
#define vi vector <int>
#define pdi pair<double, pair<int,int>>
// #define double long double
using namespace std;
using ll = long long;
const int N = 1e5 + 5, base = 70;
const double inf = 1e18;
bool vis[N];
vi g[N], luu;
int n, m, k, h, x[N], y[N], c[N], arr[N];
double dist[N][base + 1];
void dfs(int u) {
if (arr[u] == 0) luu.push_back(u);
vis[u] = 1;
for (int id : g[u]) {
int v = x[id];
if (v == u) v = y[id];
if (!vis[v]) {
if (v != h) dfs(v);
else vis[v] = 1;
}
}
}
double solve(int N, int M, int K, int H, vi X, vi Y, vi C, vi ARR) {
n = N;
m = M;
k = min(K, base);
h = H;
luu.clear();
fill(vis, vis + n, 0);
for (int i = 0; i < n; ++i) {
g[i].clear();
arr[i] = ARR[i];
for (int j = 0; j <= k; ++j) dist[i][j] = inf;
}
for (int i = 0; i < m; ++i) {
x[i] = X[i];
y[i] = Y[i];
c[i] = C[i];
g[x[i]].push_back(i);
g[y[i]].push_back(i);
}
dfs(0);
if (!vis[h]) return -1;
priority_queue <pdi,vector<pdi>,greater<pdi>> pq;
dist[0][0] = 0;
pq.push({0, {0, 0}});
for (int v : luu) {
dist[v][0] = 0;
pq.push({0, {v, 0}});
}
while (!pq.empty()) {
double D = pq.top().first;
int u = pq.top().second.first;
int lap = pq.top().second.second;
pq.pop();
if (D != dist[u][lap]) continue;
for (int id : g[u]) {
int v = x[id];
if (v == u) v = y[id];
double W = D + c[id];
if (W < dist[v][lap]) {
dist[v][lap] = W;
if (v != h) pq.push({W, {v, lap}});
}
if (arr[v] == 2 && lap < k) {
W /= 2;
if (W < dist[v][lap + 1]) {
dist[v][lap + 1] = W;
if (v != h) pq.push({W, {v, lap + 1}});
}
}
}
}
double ans = inf;
for (int i = 0; i <= k; ++i) ans = min(ans, dist[h][i]);
return ans;
}
