#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <tuple>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define pb push_back
#define ll long long
#define ld long double
#define ui uint64_t
#define ar array
#define us unordered_set
#define cont(set, element) ((set).find(element) != (set).end())
/********* DEBUG *********/
template <typename T>
void outvec(const vector<T>& Z, int hi = INT_MAX) {
int count = 0;
for (const T& x : Z) {
if (count >= hi) break;
cout << x << ' ';
count++;
}
cout << "\n";
}
// overloaded function for raw arrays
template <typename T, size_t N>
void outvec(const T (&arr)[N], int hi = INT_MAX) {
int count = 0;
for (size_t i = 0; i < N; ++i) {
if (count >= hi) break;
cout << arr[i] << ' ';
count++;
}
cout << "\n";
}
/********* DEBUG *********/
struct nd{
int node;
ld cst;
int uses;
};
struct cmp {
bool operator()(const nd &x, const nd &y){
return x.uses == y.uses ? x.cst > y.cst : x.uses > y.uses;
}
};
const ll inf = 1e18;
const int MOD = 1e9+7;
const int MOD2 = 998244353;
const int mxN = 200005;
double solve(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> power){
K = min(K, 70);
ld ans = 1e18;
// cost, node, uses
priority_queue<nd, vector<nd>, cmp> pq;
pq.push({0,0,0});
// cost, node
vector<vector<pair<ld,int>>> adj(N);
for (int i = 0; i < M; i++){
adj[x[i]].pb({c[i], y[i]});
adj[y[i]].pb({c[i], x[i]});
}
// find starts
queue<int> q;
vector<bool> visited(N, false);
visited[0] = true;
q.push(0);
while (q.size()){
int nd = q.front(); q.pop();
if (power[nd] == 0){
pq.push({nd,0,0});
}
for (auto &x : adj[nd]){
if (x.second == H)
continue;
if (!visited[x.second]){
visited[x.second] = true;
q.push(x.second);
}
}
}
vector<vector<bool>> seen(N, vector<bool>(K+1, false));
int cl = 0;
while (pq.size()){
auto x = pq.top(); pq.pop();
ld cst = x.cst;
int nd = x.node;
int uses = x.uses;
//cout << "nd, cst, use: " << nd << ' ' << cst << ' ' << uses << "\n";
if (nd == H){
ans = min(ans, cst);
continue;
}
if (seen[nd][uses])
continue;
seen[nd][uses] = true;
// cost, node
for (auto &x : adj[nd]){
ld Ncst = x.first;
int Nnd = x.second;
if (!seen[Nnd][uses]){
pq.push({Nnd, cst+Ncst, uses});
}
if (power[Nnd] == 2 && uses < K && !seen[Nnd][uses+1]){
pq.push({Nnd, (cst+Ncst)/2, uses+1});
}
}
}
return ans >= 1e18 ? -1 : (double)ans;
}
