#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, l, r) for (int i = l; i < r; i++)
template <class T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
double solve(int N, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> ARR) {
K = min(K, 50);
const double INF = 1e18;
vector<pair<int, int>> G[N + 1];
bool vis[N][K + 1];
double dist[N][K + 1];
REP(i, 0, N) REP(j, 0, K + 1) vis[i][j] = false, dist[i][j] = INF;
REP(i, 0, M) G[X[i]].push_back({Y[i], C[i]}), G[Y[i]].push_back({X[i], C[i]});
REP(i, 0, K + 1) {
min_heap<pair<double, int>> pq;
REP(j, 0, N) {
if (j == 0 || ARR[j] == 0) dist[j][i] = 0;
for (auto [v, w] : G[j]) pq.push({dist[j][i] + w, v});
dist[j][i] = INF;
if (j == 0 || ARR[j] == 0) dist[j][i] = 0;
}
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (vis[u][i]) continue;
vis[u][i] = true; dist[u][i] = d;
if (i < K) dist[u][i + 1] = min(dist[u][i + 1], d / 2);
for (auto [v, w] : G[u]) {
if (dist[u][i] + w < dist[v][i]) {
dist[v][i] = dist[u][i] + w;
pq.push({dist[v][i], v});
}
}
}
}
return *min_element(dist[H], dist[H] + K + 1);
}
// int main() {
// // cout << fixed << setprecision(10) << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});
// cout << fixed << setprecision(10) << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1});
// }
