#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lld = double;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vii = vector<int>;
#define pb push_back
#define MP make_pair
#define f first
#define s second
const long double INFd = (long double)1e15;
void dfs(int nodo, vector<vpii> &g, vii &arr, vector <long 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<vpii> &g, vector <long double> &ans) {
priority_queue<pair<long double, int>, vector<pair<long double, int>>, greater<pair<long 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) 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<vpii> 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 <long double> ans(N + 1, INFd);
vector <long double> aux(N + 1, INFd);
vis[H] = true;
dfs(0, g, arr, ans, vis);
ans[0] = 0;
long double ANS = INFd, preANS = -1;
for (int i = 0; i < K; i++) {
if (ANS == preANS) break;
djks(N, H, g, ans);
aux = ans;
for (int i = 0; i < N; i++) if (i != H)
for (auto &it : g[i])
if (arr[it.f] == 2)
aux[it.f] = min(aux[it.f], (long double)((it.s + ans[i])/2));
for (int i = 0; i <= N; i++) ans[i] = min(ans[i], aux[i]);
djks(N, H, g, ans);
preANS = ANS;
for (auto &it : g[H])
ANS = min(ANS, it.s + ans[it.f]);
}
return ANS;
}
