#include<bits/stdc++.h>
using namespace std;
#include "cyberland.h"
const int maxK = 67;
const double inf = 4e18;
double solve(int N, int M, int K, int H,
vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
int KK = min(K, maxK);
vector<vector<pair<int,int>>> edge(N);
for(int i = 0; i < M; ++i){
edge[x[i]].push_back({y[i], c[i]});
edge[y[i]].push_back({x[i], c[i]});
}
vector<vector<double>> dist(N, vector<double>(KK + 1, inf));
priority_queue<
pair<pair<double,int>,int>,
vector<pair<pair<double,int>,int>>,
greater<pair<pair<double,int>,int>>
> pq;
dist[0][0] = 0;
pq.emplace(make_pair(0, 0), 0);
while(!pq.empty()){
auto [AAA, nownode] = pq.top();
auto [nowdist, nowK] = AAA;
pq.pop();
if(nowdist > dist[nownode][nowK]) continue;
if(arr[nownode] == 0 && nowdist > 0){
if(dist[nownode][nowK] > 0){
dist[nownode][nowK] = 0;
pq.emplace(make_pair(0, nowK), nownode);
}
}
if(arr[nownode] == 2 && nowK < KK){
double neww = nowdist / 2.0;
if(dist[nownode][nowK + 1] > neww){
dist[nownode][nowK + 1] = neww;
pq.emplace(make_pair(neww, nowK + 1), nownode);
}
}
for(auto [tonode, todist] : edge[nownode]){
double nd = nowdist + todist;
if(dist[tonode][nowK] > nd){
dist[tonode][nowK] = nd;
pq.emplace(make_pair(nd, nowK), tonode);
}
}
}
double out = inf;
for(int i = 0; i <= KK; ++i){
out = min(out, dist[H][i]);
}
if(out == inf) return -1;
return out;
}
