#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=100000;
vector<vector<pair<int,double>>> adj;
bool alc[MAXN], vis[MAXN];
void dfs(int u){
alc[u]=true;
for(auto [v,t]:adj[u]){
if(!alc[v]){
dfs(v);
}
}
}
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) {
memset(alc, 0, sizeof(alc));
memset(vis, 0, sizeof(vis));
adj.clear();
adj.resize(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]});
}
dfs(0);
if(!alc[H])return -1;
set<tuple<double,int,int>> q2;
q2.insert({0,0,0});
vector<vector<double>> dist(N, vector<double>(K+1, 1e18));
dist[0][0]=0;
while(!q2.empty()){
auto [d,k,u]=*q2.begin();
q2.erase(q2.begin());
if(d>dist[u][k])continue;
if(u==H)continue;
for(auto [v,t]:adj[u]){
if(arr[v]==2&&k+1<=K){
if(dist[v][k+1]>(dist[u][k]+t)/2){
dist[v][k+1]=(dist[u][k]+t)/2;
q2.insert({(d+t)/2,k+1,v});
}
}
if(dist[v][k]>dist[u][k]+t){
if(arr[v]==0)dist[v][k]=0;
else dist[v][k]=dist[u][k]+t;
q2.insert({d+t,k,v});
}
}
}
return *min_element(dist[H].begin(), dist[H].end());
}
