#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], tdp[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] = tdp[i] = -1;
queue<int> qq;
dp[0] = 0;
qq.push(0);
while (!qq.empty()) {
int v = qq.front(); qq.pop();
for (auto [u, w] : g[v]) {
if (dp[u] != -1)
continue;
dp[u] = 0;
qq.push(u);
}
}
for (int i = 0; i < n; i++)
if (arr[i] != 0 && i != 0)
dp[i] = -1;
ld ans = 1e18;
for (int i = 0; i <= k; i++) {
for (int j = 0; j < n; j++) {
if (dp[j] == -1) continue;
if (arr[j] == 2) dp[j] /= 2;
}
set<pair<int, ld>> st;
for (int j = 0; j < n; j++)
if (dp[j] != -1)
for (auto [u, w] : g[j]) {
ld ndp = dp[j] + w;
if (tdp[u] != -1 && tdp[u] <= ndp) continue;
st.erase({u, tdp[u]});
tdp[u] = ndp;
st.insert({u, tdp[u]});
}
while (!st.empty()) {
int v = st.begin()->first;
st.erase(st.begin());
for (auto [u, w] : g[v]) {
ld ndp = tdp[v] + w;
if (tdp[u] != -1 && tdp[u] <= ndp) continue;
st.erase({u, tdp[u]});
tdp[u] = ndp;
st.insert({u, tdp[u]});
}
}
for (int j = 0; j < n; j++) {
dp[j] = tdp[j];
tdp[j] = -1;
}
if (dp[h] != -1)
ans = min(ans, dp[h]);
}
for (int i = 0; i < n; i++)
g[i].clear();
if (ans == 1e18)
ans = -1;
return ans;
}
