#include "cyberland.h"
// #include "stub.cpp"
#include <bits/stdc++.h>
#include <vector>
#pragma GCC optimize("Ofast")
#define lg long long
#define ld long double
#define ff first
#define sf second
using namespace std;
const lg N = 1e5+5, K = 71;
ld dist[N][K];
lg in_queue[N][K];
vector<array<lg, 2>> adj[N];
double solve(int n, int m, int k, int h, std::vector<int> g, std::vector<int> r, std::vector<int> d, std::vector<int> t)
{
k = min(k, 70);
for(int i = 0; i < n; i++) adj[i].clear();
for(int i = 0; i < m; i++)
{
adj[g[i]].push_back({r[i], d[i]});
adj[r[i]].push_back({g[i], d[i]});
}
adj[h].clear();
for(int i = 0; i < n; i++)
{
for(int j = 0; j <= k; j++)
{
dist[i][j] = 1e18;
in_queue[i][j] = 0;
}
}
dist[0][k] = 0;
priority_queue<pair<ld, lg>> pq[71];
pq[k].push({-dist[0][k], 0});
in_queue[0][k] = 1;
for(int i = k; i >= 0; i--)
{
while(pq[i].size())
{
pair<ld, lg> p = pq[i].top();
pq[i].pop();
in_queue[p.sf][i] = 0;
for(auto [it, c] : adj[p.sf])
{
ld cost = dist[p.sf][i]+c;
if(t[it] == 0) cost = 0;
if(t[it] == 2 && i > 0 && dist[it][i-1] > (cost)/2.0)
{
dist[it][i-1] = cost/2.0;
if(!in_queue[it][i-1])pq[i-1].push({-dist[it][i-1], it});
in_queue[it][i-1] = true;
}
if(dist[it][i] > cost)
{
dist[it][i] = cost;
if(!in_queue[it][i])pq[i].push({-dist[it][i], it});
in_queue[it][i] = true;
}
}
}
}
ld ans = 1e18;
for(int i = 0; i <= k; i++)
{
ans = min(ans, dist[h][i]);
}
if(ans > 1e15)
{
ans = -1;
}
return ans;
}
