#include "cyberland.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
// #include<atcoder/all>
// using namespace atcoder;
// using mint=atcoder::modint998244353;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
// #define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
struct fast_io{fast_io(){std::cin.tie(nullptr)->sync_with_stdio(false);}}_;
template<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>;
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<pair<int,int>>> g(N);
rep(i,M){
g[x[i]].push_back({y[i],c[i]});
g[y[i]].push_back({x[i],c[i]});
}
// vector<bool> flg(N);
// {
// stack<int> q;
// q.push(0);
// while(q.size()){
// int p=q.top();q.pop();
// flg[p]=1;
// for(auto&&[e,c]:g[p]){
// if(flg[e])continue;
// q.push(e);
// }
// }
// if(!flg[H]){
// return -1;
// }
// }
K=min(K,50);
vector<vector<double>> d(K+1,vector<double>(N,1e18));
pqmin<tuple<double,int,int>> pq;
d[0][0]=0;pq.push({0,0,0});
rng(i,1,N){
if(arr[i]==0){
d[0][i]=0;
pq.push({0,0,i});
}
}
while(pq.size()){
auto[cost,k,p]=pq.top();pq.pop();
for(auto&&[e,c]:g[p]){
if(d[k][e]>cost+c){
d[k][e]=cost+c;
pq.push({d[k][e],k,e});
}
if(arr[e]==2&&k<K){
double t=(cost+c)/double(2.0);
if(d[k+1][e]>t){
d[k+1][e]=t;
pq.push({d[k+1][e],k+1,e});
}
}
}
}
double ans=1e18;
rep(i,K+1)ans=min(ans,d[i][H]);
if(ans>1e17)return -1;
else return ans;
}
