#include "cyberland.h"
/* * In the name of GOD */
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define mk make_pair
const ll N = 2e5 + 10, INF = 2e18 + 10;
vector <pair <int, ll>> g[N];
ld dis[N], od[N], x[N];
int n, h;
bool vis[N];
vector <int> ww;
void dijkstra() {
priority_queue <pair <ld, int>> q;
for (int s = 0; s < n; s++)
q.push(make_pair((ld)-1.0 * dis[s], s));
while (!q.empty()) {
pair <ld, int> p = (q.top());
int x = p.S;
q.pop();
if (dis[x] != -1 * p.F || x == h)
continue;
ld d = dis[x];
for (auto [y, w] : g[x]) {
if (dis[y] <= d + w) {
continue;
}
dis[y] = d + w;
q.push(make_pair(-1 * dis[y], y));
}
}
}
void dfs(int v) {
vis[v] = true;
for (auto [u, w] : g[v]) {
if (!vis[u])
dfs(u);
}
}
void dfs2(int v) {
vis[v] = true;
ww.push_back(v);
for (auto [u, w] : g[v]) {
if (!vis[u] && u != h)
dfs2(u);
}
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
K = min(K, 70);
n = N;
h = H;
for (int i = 0; i <= n; i++)
g[i].clear(), vis[i] = false;
for (int i = 0; i < M; i++) {
g[x[i]].push_back(mk(y[i], c[i]));
g[y[i]].push_back(mk(x[i], c[i]));
}
dfs(0);
if (!vis[H]) {
for (int i = 0; i <= n; i++)
g[i].clear(), vis[i] = false;
return -1;
}
for (int i = 0; i < n; i++) {
dis[i] = INF;
}
for (int i = 0; i <= n; i++)
vis[i] = false;
ww.clear();
dfs2(0);
for (int i : ww) {
if (i == 0 || arr[i] == 0)
dis[i] = 0;
}
ld mn = INF;
for (int i = 0; i <= K; i++) {
dijkstra();
mn = min(mn, dis[H]);
dis[H] = INF;
for (int i = 0; i < n; i++)
od[i] = dis[i];
for (int i = 0; i < n; i++) {
if (arr[i] == 2) {
ld mnn = INF;
for (auto [j, w] : g[i]) {
mnn = min(mnn, od[j] + w);
}
dis[i] = min(dis[i], (mnn) / (ld)2);
}
}
}
for (int i = 0; i <= n; i++)
g[i].clear(), vis[i] = false;
return mn;
}
