#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>;
using pdi = pair<pair<long double, int>, 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;
}
void dijkstra(int N, int H, vector<vpii> &g, vii &arr, vector<long double> &ans) {
priority_queue<pdi, vector<pdi>, greater<pdi>> pq;
bool vis[N + 1][2];
for (int i = 0; i <= N; i++)
vis[i][0] = vis[i][1] = false;
vis[H][0] = vis[H][1] = true;
djks(N, H, g, ans);
for (int i = 0; i < N; i++)
if (i != H) pq.push(MP(MP(ans[i], 0), i));
while (!pq.empty()) {
while (!pq.empty() && vis[pq.top().s][pq.top().f.s]) pq.pop();
if (pq.empty()) break;
auto p = pq.top();
vis[p.s][p.f.s] = true;
ans[p.s] = min(ans[p.s], p.f.f);
for (auto &it : g[p.s]) {
if (vis[it.f][p.f.s]) continue;
pq.push(MP(MP(it.s + p.f.f, p.f.s), it.f));
}
if (p.f.s == 0) for (auto &it : g[p.s]) {
if (arr[it.f] != 2 || vis[it.f][1]) continue;
pq.push(MP(MP((long double)((it.s + p.f.f)/2), 1), 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);
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;
dijkstra(N, H, g, arr, ans);
preANS = ANS;
for (auto &it : g[H])
ANS = min(ANS, it.s + ans[it.f]);
}
return ANS;
}
/*
int main() {
vii x = {1, 2}, y = {2, 0}, c = {12, 4}, arr = {1, 2, 1};
cout << solve(3, 2, 30, 2, x,y,c,arr);
}*/
