#include <cassert>
#include <cstdlib>
#include <iostream>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
typedef vector<int> vi;
const double eps = 1e-8;
double solve(int n, int m, int k, int e, vi x, vi y, vi c, vi a) {
vector<vi> g(n);
for (int h = 0; h < m; h++) {
g[x[h]].push_back(h);
g[y[h]].push_back(h);
}
vector<bool> alive(n);
vector<double> d(n);
k = min(k, 100);
auto run = [&]() {
priority_queue<pair<double, int>> pq;
for (int i = 0; i < n; i++)
if (alive[i]) pq.push({-d[i], i});
while (pq.size()) {
auto [v, i] = pq.top();
pq.pop();
v *= -1;
if (abs(v - d[i]) > eps) continue;
if (i == e) continue;
for (int h : g[i]) {
int j = i ^ x[h] ^ y[h];
if (!alive[j]) {
alive[j] = 1;
d[j] = a[j] == 0 ? 0 : d[i] + c[h];
pq.push({-d[j], j});
} else {
double nd = a[j] == 0 ? 0 : d[i] + c[h];
if (nd < d[j] - eps) {
d[j] = nd;
pq.push({-d[j], j});
}
}
}
}
};
alive[0] = 1, d[0] = 0;
run();
while (k--) {
auto nd = d;
auto nalive = alive;
for (int i = 0; i < n; i++)
if (alive[i] && i != e) {
for (int h : g[i]) {
int j = i ^ x[h] ^ y[h];
if (a[j] != 2) continue;
if (!alive[j]) {
nalive[j] = 1;
nd[j] = (d[i] + c[h]) / 2;
} else {
nd[j] = min(nd[j], (d[i] + c[h]) / 2);
}
}
}
d = nd;
alive = nalive;
run();
}
if (alive[e]) return d[e];
return -1;
}
