#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#include "cyberland.h"
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>
using namespace std;
const int N=1e5+5;
int n,m,k,val[N],fix[N],fix2[N];
pair<double,int> dist[N][105];
vector<pair<int,int>> g[N];
void dfs2(int x) {
if (fix2[x]) return;
fix2[x]=1;
for (auto AA:g[x]) {
dfs2(AA.f);
}
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
n=N; m=M; k=K;
for (int i=1; i<=n; i++) {
g[i].clear(); fix[i]=0; fix2[i]=0;
for (int j=0; j<=k; j++) {
dist[i][j]={1e18,0};
}
}
for (int i=1; i<=n; i++) {
val[i]=arr[i-1];
}
for (int i=0; i<m; i++) {
g[x[i]+1].pb({y[i]+1,c[i]});
g[y[i]+1].pb({x[i]+1,c[i]});
// cout<<x[i]+1<<" "<<y[i]+1<<endl;
}
val[1]=0;
fix2[H+1]=2;
dfs2(1);
priority_queue<pair<long long,int>> q;
for (int i=1; i<=n; i++) {
if (val[i]==0 && fix2[i]==1) {
dist[i][0].f=0;
q.push({0,i});
}
}
double ans=1e18,big=1e17;
for (int j=0; j<=k; j++) {
while (!q.empty()) {
int v=q.top().s; q.pop();
if (fix[v]) continue;
fix[v]=1;
for (auto AA:g[v]) {
int u=AA.f;
long long w=AA.s;
if (dist[u][j].f>dist[v][j].f+w) {
dist[u][j].f=dist[v][j].f+w;
dist[u][j].s=1;
q.push({-dist[u][j].f,u});
}
}
}
for (int i=1; i<=n; i++) {
if (val[i]!=2) {
dist[i][j+1]=dist[i][j];
}
else if (i!=H+1 && dist[i][j].s==1 && dist[i][j].f<big) {
dist[i][j+1].f=dist[i][j].f/2;
dist[i][j+1].s=0;
}
q.push({-dist[i][j+1].f,i});
fix[i]=0;
}
}
ans=dist[H+1][k].f;
if (dist[H+1][k].f>=big) return -1;
return ans;
}
