#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const double INF = 1e30;
double solve(int N, int M, int K, int H,
vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
K = min(K, 100);
vector<vector<pair<int,int>>> adj(N);
for(int i = 0; i < M; i++){
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
vector dp(N, vector<double>(K+1, INF));
priority_queue< tuple<double,int,int>,
vector<tuple<double,int,int>>,
greater<tuple<double,int,int>> > pq;
dp[0][0] = 0;
pq.push({0, 0, 0});
while(!pq.empty()){
auto [dist, u, used] = pq.top(); pq.pop();
if(dist > dp[u][used]) continue;
for(auto [v, w] : adj[u]){
double nd = dist + w;
if(nd < dp[v][used]){
dp[v][used] = nd;
pq.push({nd, v, used});
}
}
}
for(int i = 0; i < N; i++){
if(arr[i] == 0 && dp[i][0] > 0){
dp[i][0] = 0;
pq.push({0, i, 0});
}
}
while(!pq.empty()){
auto [dist, u, used] = pq.top(); pq.pop();
if(dist > dp[u][used]) continue;
for(auto [v, w] : adj[u]){
if(dist + w < dp[v][used]){
dp[v][used] = dist + w;
pq.push({dp[v][used], v, used});
}
if(arr[u] == 2 && used < K){
double cd = dist + w/2.0;
if(cd < dp[v][used+1]){
dp[v][used+1] = cd;
pq.push({cd, v, used+1});
}
}
}
if(u == H && arr[H]==2 && used < K){
if(dist/2.0 < dp[H][used+1]){
dp[H][used+1] = dist/2.0;
pq.push({dp[H][used+1], H, used+1});
}
}
}
double ans = INF;
for(int d = 0; d <= K; d++) ans = min(ans, dp[H][d]);
return (ans >= INF/2 ? -1.0 : ans);
}
