#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using node = pair<double, int>;
vector<vector<node>> adj;
vector<int> reach;
int dest;
void dfs(int v)
{
reach[v] = 1;
// cout << v << endl;
for(auto [u, w] : adj[v])
{
if(!reach[u] && u != dest) dfs(u);
}
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> a)
{
K = min(K, 30);
adj.assign(N, {});
reach.assign(N, 0);
for(int i = 0; i < M; i++)
{
adj[x[i]].emplace_back(y[i], c[i]);
adj[y[i]].emplace_back(x[i], c[i]);
}
dest = H;
dfs(0);
priority_queue<node, vector<node>, greater<>> q;
vector<double> dist(N, 1e18);
for(int i = 0; i < N; i++)
{
if(a[i] == 0 && reach[i]) dist[i] = 0, q.emplace(0, i);
}
double ans = 1e18;
dist[0] = 0;
q.emplace(0, 0);
while(K--)
{
priority_queue<node, vector<node>, greater<>> next_q;
vector<double> next_dist(N, 1e18);
while(!q.empty())
{
auto [c, v] = q.top(); q.pop();
if(abs(c - dist[v]) > 1e-9) continue;
if(v == H) ans = min(ans, c);
for(auto [u, w] : adj[v])
{
if(c + w < dist[u])
{
dist[u] = c + w;
q.emplace(c + w, u);
}
}
if(a[v] == 2 && c < 2 * next_dist[v])
{
next_dist[v] = c / 2;
next_q.emplace(c / 2, v);
}
}
dist = next_dist;
q = next_q;
}
// cout << ans << endl;
if(ans < 1e18) return ans;
else return -1;
}
