#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 110000;
vector<pair<int, ll>> g[N];
ld dp[N];
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);
for (int i = 0; i < m; i++) {
int u = x[i], v = y[i], w = c[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
g[h].clear();
for (int i = 0; i < n; i++)
dp[i] = -1;
dp[0] = 0;
for (int i = 0; i <= k; i++) {
for (int j = 0; j < n; j++) {
if (dp[j] == -1) continue;
if (arr[j] == 0) dp[j] = 0;
if (arr[j] == 2) dp[j] /= 2;
}
set<pair<int, ld>> st;
for (int j = 0; j < n; j++)
if (dp[j] != -1)
st.insert({j, dp[j]});
while (!st.empty()) {
int v = st.begin()->first;
st.erase(st.begin());
for (auto [u, w] : g[v]) {
ld ndp = dp[v] + w;
if (dp[u] != -1 && dp[u] <= ndp) continue;
st.erase({u, dp[u]});
dp[u] = ndp;
st.insert({u, dp[u]});
}
}
}
for (int i = 0; i < n; i++)
g[i].clear();
return dp[h];
}
