#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
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) {
//10^5
vector<pair<int,int>> adjlst[N];
long double d[N][min(K + 10,70 + 10)];
bool visited[N];
queue<pair<long double,int>> pq;
queue<int> q;
vector<int> voots;
vector<int> sootv;
for(int i = 0; i < M; i++){
adjlst[x[i]].push_back(make_pair(y[i],c[i]));
adjlst[y[i]].push_back(make_pair(x[i],c[i]));
}
for(int i = 0; i < N; i++) visited[i] = false;
for(int k = 0; k <= min(K,70); k++){
for(int i = 0; i < N; i++) d[i][k] = -1;
}
visited[0] = true;
q.push(0);
while(!q.empty()){
int i = q.front();
q.pop();
for(pair<int,int> ii : adjlst[i]){
int j = ii.first;
if(!visited[j]){
visited[j] = true;
if(arr[j] == 0) voots.push_back(j);
if(arr[j] == 2) sootv.push_back(j);
if(j != H) q.push(j);
}
}
}
voots.push_back(0);
if(!visited[H]) return -1;
for(int i : voots){
d[i][0] = 0;
pq.push(make_pair(0,i));
}
while(!pq.empty()){
long double de = pq.front().first;
int i = pq.front().second;
pq.pop();
if(d[i][0] == de && i != H){
for(pair<int,int> j : adjlst[i]){
if(d[j.first][0] == -1 || d[j.first][0] > de + j.second){
d[j.first][0] = de + j.second;
pq.push(make_pair(de + j.second, j.first));
}
}
}
}
for(int k = 1; k <= min(K,70); k++){
for(int i = 0; i < N; i++) d[i][k] = d[i][k - 1];
for(int i : sootv){
for(pair<int,int> j : adjlst[i]){
if(d[j.first][k] == -1 || d[j.first][k] > d[i][k - 1]/2 + j.second){
d[j.first][k] = d[i][k - 1]/2 + j.second;
pq.push(make_pair(d[i][k - 1]/2 + j.second, j.first));
}
}
}
while(!pq.empty()){
long double de = pq.front().first;
int i = pq.front().second;
pq.pop();
if(d[i][k] == de && i != H){
for(pair<int,int> j : adjlst[i]){
if(d[j.first][k] == -1 || d[j.first][k] > de + j.second){
d[j.first][k] = de + j.second;
pq.push(make_pair(de + j.second, j.first));
}
}
}
}
}
return d[H][min(K,70)];
}
