#include <vector>
#include <queue>
#include <tuple>
using namespace std;
template <typename T>
using min_heap = priority_queue<T,vector<T>,greater<T>>;
double solve(int n, int m, int k, int h, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){
arr[0]=0;
double fans = 1e18;
k = min(k,69);
vector<vector<pair<int,double>>> graph(n);
for (int i = 0;i < m;i++){
graph[x[i]].push_back({y[i],c[i]});
graph[y[i]].push_back({x[i],c[i]});
}
min_heap<tuple<int,double,int>> pq;
vector<bool> visited(n,0);
queue<int> q;q.push(0);
while (!q.empty()){
int node = q.front();q.pop();
if (visited[node]){continue;}
visited[node]=1;
if (arr[node]==0){pq.push({0,0,node});}
for (const auto &[next,weight]:graph[node]){if(next==h){continue;}q.push(next);}
}
vector<vector<bool>> visited2(k+1,vector<bool>(n,0));
while(!pq.empty()){
const auto [ck,cdist,node] = pq.top();pq.pop();
if (node==h){fans = min(fans,cdist);continue;}
if (visited2[ck][node]){continue;}
visited2[ck][node]=1;
for (const auto &[next,weight]:graph[node]){
if (!visited2[ck][next]){
pq.push({ck,cdist+weight,next});
}
if (arr[next]==2){
if (ck < k and !visited2[ck+1][next]){
pq.push({ck+1,(cdist+weight)/2,next});
}
}
}
}
if (fans>=1e18){return -1;}
return fans;
}
