#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
const ld inf = numeric_limits<ld>::max();
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>>> 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<vector<ld>> v(N,vector<ld>(K+1,inf));
v[0][0]=0;
queue<pair<int,int>> q;
q.push({0,0});
while(!q.empty()){
pair<int,int> current = q.front();
q.pop();
for(pair<int,int> p:adj[current.first]){
if(arr[p.first]==0&&v[p.first][current.second]!=0){
v[p.first][current.second]=0;
if(p.first!=H)q.push({p.first,current.second});
continue;
}
if(v[current.first][current.second]+p.second<v[p.first][current.second]){
v[p.first][current.second]=v[current.first][current.second]+p.second;
if(p.first!=H)q.push({p.first,current.second});
}
if(current.second!=K&&arr[p.first]==2){
if(v[current.first][current.second]+p.second<2*v[p.first][current.second+1]){
v[p.first][current.second+1]=(ld)(v[current.first][current.second]+p.second)/2;
if(p.first!=H)q.push({p.first,current.second+1});
}
}
}
}
ld ans=inf;
for(int i=0;i<K+1;i++){
ans = min(ans,v[H][i]);
}
return (ans==inf?-1:ans);
}
