#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lld = double;
using pid = pair<int, double>;
using vpid = vector<pid>;
using vii = vector<int>;
#define pb push_back
#define MP make_pair
#define f first
#define s second
const double INFd = (double)1e15;
void dfs(int nodo, vector<vpid> &g, vii &arr, vector <double> &ans, vector <bool> &vis) {
if (arr[nodo] == 0) ans[nodo] = 0;
vis[nodo] = true;
for (auto &it : g[nodo]) {
if (vis[it.f]) continue;
dfs(it.f, g, arr, ans, vis);
}
return;
}
void djks(int N, int H, vector<vpid> &g, vector <double> &ans, vector<bool> &VIS) {
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
bool vis[N + 1];
for (int i = 0; i <= N; i++) vis[i] = false;
vis[H] = true;
for (int i = 0; i < N; i++)
if (i != H && VIS[i]) pq.push(MP(ans[i], i));
while (!pq.empty()) {
while (!pq.empty() && vis[pq.top().s]) pq.pop();
if (pq.empty()) break;
auto p = pq.top();
vis[p.s] = true;
ans[p.s] = min(ans[p.s], p.f);
for (auto &it : g[p.s]) {
if (vis[it.f]) continue;
pq.push(MP(it.s + p.f, it.f));
}
}
return;
}
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) {
vector<vpid> g(N + 1);
for (int i = 0; i < M; i++) {
g[x[i]].pb(MP(y[i], c[i]));
g[y[i]].pb(MP(x[i], c[i]));
}
vector <bool> vis(N + 1, false);
vector <double> ans(N + 1, INFd);
vector <double> aux(N + 1, INFd);
vis[H] = true;
dfs(0, g, arr, ans, vis);
ans[0] = 0;
K = min(K, 80);
for (int i = 0; i < K; i++) {
djks(N, H, g, ans, vis);
aux = ans;
for (int i = 0; i < N; i++)
if (i != H && vis[i] && arr[i] == 2)
for (auto &it : g[i])
if (it.f != H)
aux[i] = min(aux[i], (double)((it.s + ans[it.f])/2));
for (int i = 0; i <= N; i++) ans[i] = min(ans[i], aux[i]);
}
djks(N, H, g, ans, vis);
double ANS = INFd;
for (auto &it : g[H])
if (vis[it.f])
ANS = min(ANS, (double)(it.s + ans[it.f]));
if (ANS == INFd) ANS = -1;
return ANS;
}
