#include "cyberland.h"
#include <tuple>
#include <vector>
#include <queue>
#include <utility>
#define MAX_N 100001
#define MAX_M 200001
#define MAX_K 71
int head[MAX_N], nxt[MAX_M], vv[MAX_M];
int ds[MAX_N];
int ds_find(int i){return ds[i]==i?i:(ds[i]=ds_find(ds[i]));}
double ww[MAX_M], d[MAX_N][MAX_K],p2[MAX_K];
int i = 1;
void link(int u, int v, int w)
{
nxt[i] = head[u];
vv[i] = v;
ww[i] = w;
head[u] = i++;
}
double solve(int n, int m, int kk, 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)head[i]=0,ds[i]=i;
i=1;
p2[0]=1;for(int j=1;j<MAX_K;++j)p2[j]=p2[j-1]/2;
if (kk >= MAX_K) kk = MAX_K - 1;
for (int i = 0; i < m; ++i) ds[ds_find(y[i])]=ds_find(x[i]), link(x[i], y[i], c[i]), link(y[i], x[i], c[i]);
if (ds_find(0) != ds_find(h)) return -1;
for (int i = 0; i < n; ++i)
for (int j = 0; j <= kk; ++j)
d[i][j] = 1e18;
arr[0]=0;
std::priority_queue<std::tuple<double, int, int> >pq;
auto nq = [&](double cost, int u, int k) { if (cost<d[u][k])d[u][k]=cost,pq.emplace(-d[u][k],u,k); };
nq(0,h,0);
while (pq.size())
{
auto[c,u,k]=pq.top();pq.pop();c*=-1;
if (d[u][k]!=c)continue;
if(arr[u]==0)return c;
for(int j=head[u];j;j=nxt[j])
{
int v=vv[j];
double w=ww[j]*p2[k];
nq(c+w, v, k);
if(arr[u]==2&&k+1<=kk)
nq(c+w/2,v,k+1);
}
}
return -1;
}
