#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'
#include "stub.cpp"
struct DSU {
int n; vector<int> p, sz;
DSU(int n) : p(n), sz(n, 1) {
iota(all(p), 0);
}
int find(int v) {
return v == p[v] ? v : p[v] = find(p[v]);
}
bool unite(int u, int v) {
u = find(u), v = find(v);
if(u == v) return false;
if(sz[u] < sz[v]) swap(u, v);
p[v] = u;
sz[u] += sz[v];
return true;
}
};
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> a) {
vector<vector<ar<int, 2>>> adj(n);
DSU dsu(n);
for(int i = 0; i < m; i++) {
adj[x[i]].pb({y[i], c[i]});
adj[y[i]].pb({x[i], c[i]});
if(x[i] != h && y[i] != h) {
dsu.unite(x[i], y[i]);
}
}
k = min(k, 70);
vector<vector<double>> d(n, vector<double>(k + 1, 1e18));
priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<>> pq;
d[0][0] = 0;
pq.push({0, 0, 0});
double nc;
while(!pq.empty()) {
auto [d_v_k, k, v] = pq.top();
pq.pop();
if(d_v_k != d[v][k] || v == h) continue;
for(auto [to, c] : adj[v]) {
if(a[to] == 0) {
d[to][k] = 0;
pq.push({d[to][k], k, to});
}
nc = d[v][k] + c;
if(d[to][k] > d[v][k] + c) {
d[to][k] = d[v][k] + c;
pq.push({d[to][k], k, to});
}
nc /= 2;
if(a[to] == 2 && d[to][k + 1] > nc) {
d[to][k + 1] = nc;
pq.push({d[to][k + 1], k + 1, to});
}
}
}
double ans = 1e18;
for(int i = 0; i <= k; i++) {
ans = min(ans, d[h][i]);
}
if(ans == 1e18) ans = -1;
return ans;
}
