#include "cyberland.h"
// #include <cassert>
// #include <cstdio>
#include "bits/stdc++.h"
#define ff first
#define ss second
using namespace std;
const double inf = 1e15;
double solve(int n,int m,int k,int h,vector <int> x,vector <int> y,vector <int> c,vector <int> arr){
vector <pair<int,int>> g[m+1];
for (int i = 0;i < m;i++){
g[x[i]].push_back({y[i],c[i]});
g[y[i]].push_back({x[i],c[i]});
}
queue <int> q;
vector <bool> vs(n);
vs[0] = 0;
q.push(0);
while (!q.empty()){
int nd = q.front();
q.pop();
if (nd == h)
continue;
for (auto [to,w] : g[nd]){
if (!vs[to]){
vs[to] = 1;
q.push(to);
}
}
}
if (!vs[h])
return -1.0;
k = min(k,70);
vector <vector <double>> d(n,vector <double> (k+1,inf));
priority_queue <pair <double,pair<int,int>>> pq;
d[0][0] = 0;
pq.push({0,{0,0}});
for (int i = 1;i < n;i++){
if (vs[i] && !arr[i]){
pq.push({0,{0,0}});
d[i][0] = 0;
}
}
while (!pq.empty()){
int nd = pq.top().ss.ff;
double w = pq.top().ff;
int k1 = pq.top().ss.ss;
if (nd == h)
pq.pop();
continue;
if (d[nd][k1] < -w)
continue;
for (auto v : g[nd]){
int to = v.ff;
double w1 = v.ss;
if (d[nd][k1]+w1 < d[to][k1]){
d[to][k1] = d[nd][k1] + w1;
pq.push({-d[to][k1],{to,k1}});
}
if (k1 < k && arr[to] == 2){
double h = (d[nd][k1]+w1)/2.0;
if (d[to][k1+1] > h){
d[to][k1+1] = h;
pq.push({-h,{to,k1+1}});
}
}
}
}
double p = inf;
for (int i = 0;i <= k;i++){
p = min(p,d[h][i]);
}
return p;
}
//int main() {
// freopen("file.in","r",stdin);
// int T;
// assert(1 == scanf("%d", &T));
// while (T--){
// int N,M,K,H;
// assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
// std::vector<int> x(M);
// std::vector<int> y(M);
// std::vector<int> c(M);
// std::vector<int> arr(N);
// for (int i=0;i<N;i++)
// assert(1 == scanf("%d", &arr[i]));
// for (int i=0;i<M;i++)
// assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
// printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
// }
//}
