#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1'000'000'000'000'000'000;
void dfs(ll v, ll h, vector<vector<pair<ll, ll>>>& g, vector<bool>& used) {
used[v] = true;
if (v == h) {
return;
}
for (auto[i, _] : g[v]) {
if (!used[i]) {
dfs(i, h, g, used);
}
}
}
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<vector<pair<ll, ll>>> g(n);
for (ll i = 0; i < m; i++) {
g[x[i]].emplace_back(y[i], c[i]);
g[y[i]].emplace_back(x[i], c[i]);
}
vector<bool> used(n, false);
dfs(0, h, g, used);
if (!used[h]) {
return -1;
}
vector<double> dist(n, INF);
dist[0] = 0;
for (ll i = 0; i < n; i++) {
if (arr[i] == 0 && used[i]) {
dist[i] = 0;
}
}
if (k > 70) {
k = 70;
}
for (ll nd = 0; nd <= k; nd++) {
set<pair<double, ll>> pq;
for (ll i = 0; i < n; i++) {
if (dist[i] != INF) {
pq.insert(make_pair(dist[i], i));
}
}
while (!pq.empty()) {
auto[d, v] = *pq.begin();
pq.erase(pq.begin());
if (v == h) {
continue;
}
for (auto[i, c] : g[v]) {
if (c + d < dist[i]) {
pq.erase(make_pair(dist[i], i));
dist[i] = c + d;
pq.insert(make_pair(dist[i], i));
}
}
}
if (nd == k) {
continue;
}
vector<pair<ll, double>> upd;
for (ll i = 0; i < n; i++) {
if (arr[i] == 2 && dist[i] != INF) {
dist[i] /= 2;
for (auto[v, c] : g[i]) {
upd.emplace_back(v, c + dist[i]);
}
dist[i] = INF;
}
}
for (auto[v, d] : upd) {
if (dist[v] > d) {
dist[v] = d;
}
}
}
return dist[h];
}
