#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
const ll INF=1e18;
#define pb push_back
#define MAXN (int)1e5
vector<bool> reachable(MAXN,false);
vector<vector<pair<int,ld>>> adj(MAXN);
void dfs(int n, int H) {
if (reachable[n] or n==H) return;
reachable[n]=true;
for (auto u : adj[n]) {
auto [a,ignore]=u;
dfs(a,H);
}
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
K=min(100,K);
priority_queue<tuple<ld,int,int>,vector<tuple<ld,int,int>>,greater<tuple<ld,int,int>>> q;
for (int i=0;i<M;i++) {
adj[x[i]].pb({y[i],(ld)c[i]});
adj[y[i]].pb({x[i],(ld)c[i]});
}
dfs(0,H);
vector<vector<ld>> distance(N+1,vector<ld>(K+1,(ld)INF));
for (int i=0;i<N;i++) {
if (arr[i]==0 and reachable[i]) {
for (int j=0;j<=K;j++) distance[i][j]=0;
q.push({0.0,i,0});
}
}
for (int i=0;i<=K;i++) distance[0][i]=0;
q.push({0.0,0,0});
while (!q.empty()) {
auto [d,a,k]=q.top(); q.pop();
if (d>distance[a][k]) continue;
if (a==H) continue;
for (auto u : adj[a]) {
auto [b,w]=u;
if (arr[b]==2) {
if (k+1<=K) {
if ((distance[a][k]+w)/2<distance[b][k+1]) {
distance[b][k+1]=(distance[a][k]+w)/2;
q.push({distance[b][k+1],b,k+1});
}
}
if (distance[a][k]+w<distance[b][k]) {
distance[b][k]=distance[a][k]+w;
q.push({distance[b][k],b,k});
}
} else {
if (distance[a][k]+w<distance[b][k]) {
distance[b][k]=distance[a][k]+w;
q.push({distance[b][k],b,k});
}
}
}
}
reachable.assign(MAXN,false);
for (int i=0;i<N;i++) adj[i].clear();
ld ans=(ld)INF;
for (int i=0;i<=K;i++) ans=min(ans,distance[H][i]);
ans=(ans==(ld)INF) ? -1 : ans;
return ans;
}
