#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sort undefined_function // To use stable_sort instead sort
#define bpc __builtin_popcount
#define ull unsigned long long
#define ld double
#define ll long long
#define mp make_pair
#define F first
#define S second
#pragma GCC optimize("O3")
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 0
#include <cyberland.h>
#endif
using namespace __gnu_pbds;
using namespace std;
typedef tree<long long, null_type, less_equal<long long>,
rb_tree_tag, tree_order_statistics_node_update> Tree;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll INF = 9223372036854775807LL;
const ll inf = 2147483647;
const ll MOD = 998244353; //[998244353, 1e9 + 7, 1e9 + 13]
const ld PI = acos(-1);
const ll NROOT = 800;
ll binpow(ll a, ll b, ll _MOD = -1) {
if (_MOD == -1)
_MOD = MOD;
ll res = 1;
for (; b; b /= 2, a *= a, a %= _MOD)
if (b & 1) res *= a, res %= _MOD;
return res;
}
void set_IO(string s) {
#ifndef LOCAL
string in = s + ".in";
string out = s + ".out";
freopen(in.c_str(), "r", stdin);
freopen(out.c_str(), "w", stdout);
#endif
}
bool dataOverflow(ll a, ll b) {return (log10(a) + log10(b) >= 18);}
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);}
ll ceil(ll a, ll b) {return (a + b - 1) / b;}
ll invmod(ll a) {return binpow(a, MOD - 2);}
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> arr) {
vector<vector<pair<int, ld>>> g(N);
for (int i = 0; i < M; i ++) {
g[x[i]].push_back({y[i], c[i]});
g[y[i]].push_back({x[i], c[i]});
}
K = min(K, 90);
vector<double> power(K + 1);
power[0] = 1.0;
for (int i = 1; i <= K; i ++)
power[i] = power[i - 1] * 0.5;
vector<vector<ld>> dis(N, vector<ld> (K + 1, 1e18));
using T = pair<ld, pair<int, int>>;
priority_queue<T, vector<T>, greater<T>> q;
dis[0][0] = 0;
q.push({0, {0, 0}});
queue<int> Q;
Q.push(0);
vector<int> vis(N);
while (!Q.empty()) {
int node = Q.front();
Q.pop();
if (vis[node])
continue;
vis[node] = 1;
if (node == H)
continue;
if (arr[node] == 0) {
q.push({0, {0, node}});
dis[node][0] = 0;
}
for (auto &[to, _] : g[node])
Q.push(to);
}
if (!vis[H])
return -1;
double ans = 1e18;
for (int iter = 0; iter <= K; iter ++) {
priority_queue<T, vector<T>, greater<T>> tmp;
while (!q.empty()) {
ld d = q.top().F;
auto [used, node] = q.top().S;
q.pop();
if (node == H)
continue;
if (dis[node][used] < d)
continue;
for (auto &[to, w] : g[node]) {
if (dis[to][used] > d + (1.0 * w)) {
q.push({d + (1.0 * w), {used, to}});
dis[to][used] = d + (1.0 * w);
}
if (used > K)
continue;
if (arr[node] == 2 && dis[to][used + 1] > (d * 0.5 + (1.0 * w))) {
tmp.push({d * 0.5 + (1.0 * w), {used + 1, to}});
dis[to][used + 1] = (d * 0.5) + (1.0 * w);
}
}
}
swap(tmp, q);
}
for (auto &val : dis[H])
ans = min(ans, val);
return ans;
}
