#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<bool> isReachable;
void dfs(ll v, vector<vector<pair<ll,double>>>& adj, ll H) {
isReachable[v] = true;
if(v == H) return;
for(pair<ll,double> u : adj[v]) {
if(!isReachable[u.first]) {
dfs(u.first, adj, H);
}
}
}
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<ll,double>>> adj(N);
for (int i = 0; i < M; i++) {
adj[x[i]].emplace_back(y[i], c[i]);
adj[y[i]].emplace_back(x[i], c[i]);
}
isReachable.clear();
isReachable.resize(N);
dfs(0, adj, H);
if(!isReachable[H]) return -1;
K = min(K, 100);
priority_queue<tuple<double,ll,ll>, vector<tuple<double,ll,ll>>, greater<>> pq;
vector<vector<double>> dist(N + 10, vector<double>(K + 10, 1e18));
vector<double> divBy = {1};
for(int i = 0; i < K + 10; i++) {
divBy.push_back(divBy[i]/2);
}
pq.emplace(0, H, K);
while(!pq.empty()) {
double curDistance = get<0>(pq.top());
ll curNode = get<1>(pq.top());
ll curK = get<2>(pq.top());
pq.pop();
if(curDistance > dist[curNode][curK]) continue;
if(curNode == 0 || arr[curNode] == 0) return curDistance;
for(auto u : adj[curNode]) {
if(isReachable[u.first]) {
double newDistance = curDistance + u.second * divBy[K - curK];
if(newDistance < dist[u.first][curK]) {
dist[u.first][curK] = newDistance;
pq.emplace(newDistance, u.first, curK);
}
if(arr[u.first] == 2 && curK > 0) {
double betterDistance = curDistance + u.second * divBy[K - curK + 1];
if(betterDistance < dist[u.first][curK - 1]) {
dist[u.first][curK - 1] = betterDistance;
pq.emplace(betterDistance, u.first, curK - 1);
}
}
}
}
}
return -1;
}
