#include <bits/stdc++.h>
using namespace std;
double pre[100];
double solve (int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
k = min(k, 70);
pre[0] = 1;
for(int i = 1; i <= k;i++) {
pre[i] = pre[i-1]/2;
}
long double dist[n][k + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
dist[i][j] = 1e18;
}
}
dist[0][k] = 0;
vector <pair <int, long double>> 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]});
}
priority_queue <pair <long double, int>, vector <pair <long double, int>>, greater <pair <long double, int>>> pq[k + 1];
pq[k].push({0, 0});
for (int i = k; i >= 0; i--) {
while (!pq[i].empty()) {
auto l = pq[i].top(); pq[i].pop();
if (dist[l.second][i] < l.first) continue;
if (l.second == h) continue;
for (auto j : adj[l.second]) {
long double sum = l.first + j.second;
if (dist[j.first][i] > sum) {
dist[j.first][i] = sum; pq[i].push({sum, j.first});
}
if (arr[j.first] == 0) {
sum = 0;
if (dist[j.first][i] > sum) {
dist[j.first][i] = sum; pq[i].push({sum, j.first});
}
} else if (arr[j.first] == 1) {
continue;
} else {
if (i == 0) continue;
sum *= pre[1];
if (dist[j.first][i - 1] > sum) {
dist[j.first][i - 1] = sum;
pq[i - 1].push({sum, j.first});
}
}
}
}
}
long double mn = 1e18;
for (int i = 0; i <= k; i++) mn = min(mn, dist[h][i]);
if (mn == 1e18) {
return -1;
}
return mn;
}
