#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define iter(a) a.begin(), a.end()
#define pb(a) emplace_back(a)
#define mp(a, b) make_pair(a, b)
#define ff first
#define ss second
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define SZ(a) int(a.size())
#ifdef LOCAL
void debug(){cerr << "\n";}
template<class T, class ... U> void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cerr << *l << " ", l++;
cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif
typedef long long ll;
typedef long double ld;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const ll MOD = 1000000007;
const ll MAX = 2147483647;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.ff << ',' << p.ss << ')';
}
ll ifloor(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a < 0) return (a - b + 1) / b;
else return a / b;
}
ll iceil(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a > 0) return (a + b - 1) / b;
else return a / b;
}
double solve(int n, int m, int K, int H, vector<int> U, vector<int> V, vector<int> W, vector<int> arr){
K = min(K, 70);
vector<ld> frac(K + 1); // 2^-i
frac[0] = 1;
for(int i = 1; i <= K; i++) frac[i] = frac[i - 1] / 2;
vector<vector<pii>> g(n);
for(int i = 0; i < m; i++){
g[U[i]].pb(mp(V[i], W[i]));
g[V[i]].pb(mp(U[i], W[i]));
}
vector<bool> ok(n);
{
queue<int> q;
q.push(0);
ok[0] = true;
while(!q.empty()){
int now = q.front();
q.pop();
for(auto [v, w] : g[now]){
if(v == H) continue;
if(ok[v]) continue;
ok[v] = true;
q.push(v);
}
}
}
vector<vector<ld>> dis(n, vector<ld>(K + 1, 1e100));
priority_queue<pair<ld, pii>, vector<pair<ld, pii>>, greater<>> pq;
vector<vector<bool>> vst(n, vector<bool>(K + 1));
dis[H][0] = 0;
pq.push(mp(0, mp(H, 0)));
auto relax = [&](int now, int k, ld d){
if(k > K) return;
for(auto [v, w] : g[now]){
if(v == H) continue;
if(d + w * frac[k] >= dis[v][k]) continue;
dis[v][k] = d + w * frac[k];
pq.push(mp(dis[v][k], mp(v, k)));
}
};
ld ans = 1e100;
while(!pq.empty()){
ld d = pq.top().ff;
auto [now, k] = pq.top().ss;
pq.pop();
if(vst[now][k]) continue;
if((ok[now] && arr[now] == 0) || now == 0) ans = min(ans, d);
vst[now][k] = true;
relax(now, k, d);
if(arr[now] == 2) relax(now, k + 1, d);
}
if(ans > 1e20) return -1;
else return ans;
}
