#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][K + 10];
bool visited[N];
priority_queue<pair<long double,int>,vector<pair<long double,int>>,greater<pair<long double,int>>> pq;
queue<int> q;
vector<int> voots;
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 <= K; 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(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.top().first;
int i = pq.top().second;
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));
}
}
}
}
return d[H][0];
}
