#include "cyberland.h"
#include <iostream>
#include <vector>
#include <cmath>
#include<map>
#include <algorithm>
#include <iomanip>
#include <string>
#include<stack>
#include <set>
#include <queue>
#include <chrono>
#include<array>
#include<bitset>
#include<unordered_map>
#include<random>
#include<cassert>
#include<cstring>
using namespace std;
using ll = long long;
using db = double;
const float pi = 3.14159265359;
#define V vector
#define VI V<int>
#define P pair<int,int>
#define rep(i, a, b, step) for (int i = int(a); i <= int(b); i += step)
#define repl(i,a,b,step) for (int i = int(a); i >= int(b); i -= step)
#define prime(n) [](int x) { for (int i = 2; i *1ll* i <= x; ++i) if (x % i == 0) return false; return x > 1; }(n)
#define printall(container, ch) for (const auto& elem : container) { std::cout << elem << ch; } std::cout << std::endl;
#define sn << '\n'
#define ed << endl
#define sz size()
#define print cout <<
#define debug(x) cerr<< #x << " = " << x sn;
#define mpII map<int,int>
#define mine min_element
#define maxe max_element
#define all(v) begin(v), end(v)
#define txt freopen("snakes.in", "r", stdin); freopen("snakes.out", "w", stdout)
#define pb push_back
#define pq priority_queue
#define rev reverse
#define nuyn(a) a.erase(unique(all(a)), end(a))
#define nx next_permutation
#define pk pop_back()
#define START print "Start" sn
#define END print "End" sn
#define ff first
#define ss second
#define ts to_string
#define ub upper_bound
#define mk make_pair
#define lb lower_bound
#define testcase int t;cin>>t;while(t--)solution();
using ld = long double;
const ld inf = 1e18;
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) {
int k = min(K, 64);
V<V<ld>>dp(n, V<ld>(k + 1, inf));
queue<int>Q;
pq<pair<ld, array<int, 2>>, V<pair<ld, array<int, 2>>>, greater<>>q;
Q.push(0);
V<bool>vsQ(n);
V<V<P>>graph(n);
rep(i, 0, m - 1, 1) {
graph[x[i]].pb({ y[i],c[i] });
graph[y[i]].pb({ x[i],c[i] });
}
vsQ[0] = 1;
int u, p;
ld w;
while (!Q.empty()) {
u = Q.front();
Q.pop();
if (!a[u]) {
dp[u][0] = 0;
q.push({ 0,{0,u} });
}
for (auto& i : graph[u])if (!vsQ[i.ff] and i.ff != h) {
vsQ[i.ff] = 1;
Q.push(i.ff);
}
}
dp[0][0] = 0;
q.push({ 0,{0,0} });
pair<ld, array<int, 2>>cur;
while (!q.empty()) {
cur = q.top();
u = cur.ss[1];
p = cur.ss[0];
w = cur.ff;
q.pop();
if (dp[u][p] != w or u == h)continue;
for (auto& i : graph[u]) {
if (!a[i.ff])continue;
if (dp[i.ff][p] > w + i.ss) {
dp[i.ff][p] = w + i.ss;
q.push({ dp[i.ff][p],{p,i.ff} });
}
if (a[i.ff] > 1 and p + 1 <= k and dp[i.ff][p + 1] > ld(w + i.ss) / ld(2)) {
dp[i.ff][p + 1] = ld(w + i.ss) / ld(2);
q.push({ dp[i.ff][p + 1],{p + 1,i.ff} });
}
}
}
ld ans = *mine(all(dp[h]));
if (ans == inf)ans = -1;
return ans;
}
