#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define pb push_back
struct hi{
double val;
int k;
int u;
};
struct cmp{
bool operator()(hi a, hi b){
return a.val > b.val;
}
};
void dfs(int H, int u, vector<bool> &vis, vector<vector<pii>> &G){
if(u == H) return;
vis[u] = 1;
for(auto &[v, w] : G[u]){
if(!vis[v]) dfs(H, v, vis, G);
}
}
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<pii>> G(N);
for(int i = 0; i < M; i++){
G[x[i]].pb({y[i], c[i]});
G[y[i]].pb({x[i], c[i]});
}
vector<bool> vis(N, 0);
dfs(H, 0, vis, G);
if(!vis[H]) return -1;
K = min(K, 67);
priority_queue<hi, vector<hi>, cmp> pq;
vector<vector<double>> dist(N, vector<double>(K + 1, 1e18));
pq.push((hi){0, 0, 0});
dist[0][0] = 0;
for(int i = 0; i < N; i++){
if(arr[i] == 0 && vis[i]){
pq.push((hi){0, 0, i});
dist[i][0] = 0;
}
}
while(!pq.empty()){
auto [val, k, u] = pq.top();
pq.pop();
// cout << "HI " << val << ' ' << k << ' ' << u << '\n';
if(dist[u][k] < val) continue;
if(u == H) continue;
for(auto &[v, w] : G[u]){
if(arr[v] == 0 && dist[v][k] > 0.000){
dist[v][k] = 0.0000;
pq.push((hi){dist[v][k], k, v});
}else if(arr[v] == 2 && k + 1 <= K){
if(dist[v][k + 1] > (val + w) / 2.0000){
dist[v][k + 1] = (val + w) / 2.0000;
pq.push((hi){dist[v][k + 1], k + 1, v});
}
}
if(dist[v][k] > val + w){
dist[v][k] = val + w;
pq.push((hi){dist[v][k], k, v});
}
}
}
double d = *min_element(dist[H].begin(), dist[H].end());
// cout << dist[H][1] << ' ' << d << '\n';
if(d > 1e17) return -1;
return d;
}
