#include "cyberland.h"
#include <vector>
#include <cassert>
#include <algorithm>
#include <set>
#include <bitset>
using namespace std;
const int MAXN = 1e5 + 123;
const double INF = 1e18 + 177013;
vector<pair<int, int>> edg[MAXN];
bitset<MAXN> used;
void dfs_connect(int v, int H) {
if (used[v])
return;
used[v] = 1;
if (v == H)
return;
for (auto [u, d] : edg[v]) {
dfs_connect(u, H);
}
}
void initialize(int N, int M, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
for (int i = 0; i < N; ++i) {
edg[i].clear();
}
used = 0;
for (int i = 0; i < M; ++i) {
edg[x[i]].push_back({y[i], c[i]});
edg[y[i]].push_back({x[i], c[i]});
}
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
initialize(N, M, x, y, c, arr);
dfs_connect(0, H);
if (!used[H])
return -1;
bitset<MAXN> start;
for (int i = 0; i < N; ++i) {
start[i] = used[i] & (i == 0 || arr[i] == 0);
}
int K0 = 0;
for (int i = 0; i < N; ++i) {
if (arr[i] == 2 && used[i])
++K0;
}
K = min(K, K0);
if (K > 0 && M == N - 1) {
for (int i = 0; i < M - 1; ++i) {
assert(x[i] == i && y[i] == i + 1);
}
double ans = 0;
double mod = 1;
int cnt = 0;
for (int i = H - 1; i >= 0; --i) {
ans += 1.0 * mod * c[i];
if (arr[i] == 2 && cnt < K) {
++cnt;
mod /= 2;
}
if (start[i])
return ans;
}
assert(0);
}
vector<double> depth(N, INF);
depth[H] = 0;
set<pair<double, int>> pq;
used = 0;
pq.insert({depth[H], H});
while (pq.size()) {
auto [d, v] = *pq.begin();
if (start[v])
return d;
pq.erase(pq.begin());
for (auto [u, len] : edg[v]) {
if (d + len < depth[u]) {
pq.erase({depth[u], u});
depth[u] = d + len;
pq.insert({depth[u], u});
}
}
}
vector<pair<double, int>> rdepth;
for (int i = 0; i < N; ++i) {
if (depth[i] < INF / 2) {
rdepth.push_back({depth[i], i});
}
}
sort(rdepth.begin(), rdepth.end());
return -1;
}
