#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) {
K = min(K, 65);
int cur, num;
double d, ans = -1;
vector<pair<int, int>> adj[N];
for(int i = 0; i < M; i++) {
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
double dist[N][K+1];
for(int i = 0; i < N; i++) for(int j = 0; j <= K; j++) dist[i][j] = -1;
dist[0][0] = 0;
priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> pq;
pq.push({0, 0, 0});
while(!pq.empty()) {
tie(d, cur, num) = pq.top();
pq.pop();
if(dist[cur][num] != d) continue;
if(cur == H) continue;
for(auto i : adj[cur]) {
double nd = d+i.second;
if(arr[i.first] == 0) nd = 0;
if(dist[i.first][num] == -1 || dist[i.first][num] > nd) {
dist[i.first][num] = nd;
pq.push({nd, i.first, num});
}
if(arr[i.first] == 2) {
if(num+1 > K) continue;
nd /= 2.0;
if(dist[i.first][num+1] == -1 || dist[i.first][num+1] > nd) {
dist[i.first][num+1] = nd;
pq.push({nd, i.first, num+1});
}
}
}
}
for(int i = 0; i <= K; i++) {
if(dist[H][i] != -1) {
if(ans == -1) ans = dist[H][i];
else ans = min(ans, dist[H][i]);
}
}
return ans;
}
