#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define db long double
const int nx=1e5+5, kx=68;
const db inf=1e18;
bool vs[nx][kx], reachable[nx];
db mn[nx][kx], p[kx];
vector<pair<int, int>> adj[nx];
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) {
for (int i=0; i<N; i++) adj[i].clear(), reachable[i]=0;
K=min(K, 67);
for (int i=0; i<N; i++) for (int j=0; j<=K; j++) mn[i][j]=inf, vs[i][j]=0;
for (int i=0; i<M; i++) adj[x[i]].push_back({y[i], c[i]}), adj[y[i]].push_back({x[i], c[i]});
queue<int> q; // find reachable node from 0
q.push(0);
reachable[0]=1;
while (!q.empty())
{
auto u=q.front();
q.pop();
for (auto [v, w]:adj[u]) if (!reachable[v]&&v!=H) reachable[v]=1, q.push(v);
}
priority_queue<tuple<db, int, int>, vector<tuple<db, int, int>>, greater<tuple<db, int, int>>> pq;
pq.push({0, H, 0});
p[0]=1;
for (int i=1; i<=K; i++) p[i]=p[i-1]/2;
while (!pq.empty())
{
auto [cw, u, div]=pq.top();
pq.pop();
if (vs[u][div]) continue;
vs[u][div]=1;
if (arr[u]==0||u==0) return cw;
for (auto [v, w]:adj[u])
{
if (!reachable[v]) continue;
if (mn[v][div]>cw+w*p[div]) mn[v][div]=cw+w*p[div], pq.push({mn[v][div], v, div});
if (div<K&&arr[v]==2&&mn[v][div+1]>cw+w*p[div]) mn[v][div+1]=cw+w*p[div], pq.push({mn[v][div+1], v, div+1});
}
}
return -1;
}
