#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int st, vector<array<int,2>>(&g)[], bool vis[], int h){
vis[st]=1;
if(st==h)
return;
for(array<int,2>e:g[st]){
if(vis[e[0]])
continue;
dfs(e[0],g,vis,h);
}
}
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) {
const int mxk = 70;
k=min(k,mxk-2);
double tim[n][mxk];
for(int i = 0;i<n;i++){
for(int j = 0;j<mxk;j++){
tim[i][j]=2e18;
}
}
vector<array<int,2>>g[n];
for(int i = 0;i<m;i++){
if(x[i]!=h)
g[x[i]].push_back({y[i],c[i]});
if(y[i]!=h)
g[y[i]].push_back({x[i],c[i]});
}
bool vis[n];
fill(vis,vis+n,0);
dfs(0,g,vis,h);
priority_queue<tuple<double,int>,vector<tuple<double,int>>,greater<tuple<double,int>>>pq;
pq.push({0,0});
tim[0][0]=0;
for(int i = 0;i<n;i++){
if(vis[i]&&arr[i]==0){
pq.push({0,i});
tim[i][0]=0;
}
}
//{time,index,usedk}
int curk = 0;
while(!pq.empty()){
tuple<double,int>curr = pq.top();
pq.pop();
if(tim[get<1>(curr)][curk]<=get<0>(curr)){
continue;
}
tim[get<1>(curr)][curk]=get<0>(curr);
if(get<1>(curr)==h)
continue;
for(array<int,2>e:g[get<1>(curr)]){
pq.push({get<0>(curr)+e[1],e[0]});
}
}
while(pq.size()){
pq.pop();
}
for(int curk = 1;curk<=k;curk++){
for(int i = 0;i<n;i++){
if(!vis[i])
continue;
tim[i][curk]=tim[i][curk-1];
if(arr[i]==2&&tim[i][curk]<=2e15){
tim[i][curk]/=2;
}
pq.push({tim[i][curk],i});
}
while(!pq.empty()){
tuple<double,int>curr = pq.top();
pq.pop();
if(tim[get<1>(curr)][curk]<=get<0>(curr)){
continue;
}
tim[get<1>(curr)][curk]=get<0>(curr);
if(get<1>(curr)==h)
continue;
for(array<int,2>e:g[get<1>(curr)]){
pq.push({get<0>(curr)+e[1],e[0]});
}
}
while(pq.size()){
pq.pop();
}
}
double ans = 2e18;
for(int i = 0;i<mxk;i++){
ans=min(ans,tim[h][i]);
}
if(ans==2e18){
return -1;
}
else{
return ans;
}
}
