#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#pragma GCC optimize("ofast")
#pragma GCC optimize("unroll-loops")
const int N=1e5+50,M=66;
const ll INF=1e18;
vector<pair<int,ll>>E[N];
int n,m;
vector<int>a;
void chmn(ll &x,ll y){x=min(x,y);}
bool chmn(ld &x,ld y){bool bul=false;if(x>y)bul=true;x=min(x,y);return bul;}
ld dist[M+1][N];
double solve(int n1, int m1, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
K=min(K,M);
n=n1,m=m1;a=arr;
for(int i=0;i<m;i++){
E[x[i]].pb({y[i],(ll)c[i]});
E[y[i]].pb({x[i],(ll)c[i]});
}
for(int k=0;k<=K;k++){
for(int i=0;i<n;i++){
dist[k][i]=INF;
}
dist[k][0]=0;
}
priority_queue<pair<ld,pair<ll,ll>>>pq;
pq.push({-dist[K][0],{K,0}});
while(!pq.empty()){
pair<ld,pair<ll,ll>>temp=pq.top();pq.pop();
int k=temp.se.fi,u=temp.se.se;ld W=-temp.fi;
if(W>dist[k][u]) continue;
if(u==H) continue;
for(auto [i,w]:E[u]){
if(a[i]==0&&dist[k][i]>0){
//if(chmn(dist[k][i],(ld)0)) pq.push({-dist[k][i],{k,i}});
pq.push({0,{k,i}});dist[k][i]=0;
}
else if(k>0&&a[i]==2&&2*dist[k-1][i]>dist[k][u]+w){
dist[k-1][i]=(dist[k][u]+w)/2;
pq.push({-dist[k-1][i],{k-1,i}});
}
if(dist[k][i]>dist[k][u]+w){
dist[k][i]=dist[k][u]+w;
pq.push({-dist[k][i],{k,i}});
}
}
}
ld res=INF;for(int k=0;k<=K;k++) res=min(res,dist[k][H]);
for(int i=0;i<=n;i++){
E[i].clear();
for(int k=0;k<=K;k++){
dist[k][i]=0;
}
}
a.clear();
if(res>=INF) return (ld)-1;
return res;
}
