#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
#define mins(a, b) (a = min(a, b))
const int MXN = 1e5+5;
const double inf = 1e16;
int h;
vector<pii> g[MXN];
double dis[MXN], dis2[MXN];
bool vis[MXN];
void dfs(int v) {
vis[v] = 1;
for(auto [u, w] : g[v])
if(!vis[u] && u!=h)
dfs(u);
}
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
::h = h;
for(int i=0; i<n; i++) {
dis[i] = i ? inf : 0;
g[i].clear();
vis[i] = 0;
}
for(int i=0; i<m; i++) {
g[x[i]].push_back({y[i], c[i]});
g[y[i]].push_back({x[i], c[i]});
}
dfs(0);
for(int i=0; i<n; i++)
if(vis[i] && !arr[i])
dis[i] = 0;
double ans = inf;
for(int x=min(70, k); x>=0; x--) {
priority_queue<pair<double, int>> pq;
for(int i=0; i<n; i++) vis[i] = 0, pq.push({-dis[i], i});
while(!pq.empty()) {
double d = -pq.top().X;
int v = pq.top().Y;
pq.pop();
if(vis[v]) continue;
vis[v] = 1;
for(auto [u, w] : g[v])
if(u!=h && dis[u] > dis[v]+w)
pq.push({-(dis[u] = dis[v]+w), u});
}
for(int v=0; v<n; v++) {
dis2[v] = inf;
for(auto [u, w] : g[v])
if(arr[u]==2 && dis[u] < inf/2)
mins(dis2[v], dis[v] / 2 + w);
}
double res = x ? dis2[h] : inf;
for(auto [u, w] : g[h]) mins(res, dis[u]+w);
for(int i=0; i<n; i++) dis[i] = i==h ? inf : dis2[i];
mins(ans, res);
}
return ans < inf/2 ? ans : -1;
}
