#define _CRT_SECURE_NO_WARNINGS
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int>pi;
typedef pair<ll, ll>pl;
typedef vector<pi>vpi;
typedef vector<pl>vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<bool> vb;
const long double PI = acos(-1);
const ll oo = 2e18 + 10;
const int MOD = 1e9 + 7;
const ll N = 2e5 + 10;
#define endl '\n'
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define read(v) for (auto& it : v) scanf("%d", &it);
#define readL(v) for (auto& it : v) scanf("%lld", &it);
#define print(v) for (auto it : v) printf("%d ", it); puts("");
#define printL(v) for (auto it : v) printf("%lld ", it); puts("");
#include <vector>
vpl graph[N];
double cost[N], copCost[N], ret = double(oo);
int n, m, k, h;
bool vis[N];
vi vec;
void reset() {
for (int i = 0; i <= n; i++)
vis[i] = false, graph[i].clear();
}
void DFS1(int u) {
vis[u] = true;
for (auto& v : graph[u]) {
if (vis[v.first])
continue;
DFS1(v.first);
}
}
void DFS2(int u) {
vis[u] = true;
vec.push_back(u);
for (auto& v : graph[u]) {
if (v.first == h || vis[v.first])
continue;
DFS2(v.first);
}
}
void Dijkstra() {
priority_queue<pair<double, int>>pq;
for (int i = 0; i < n; i++)
pq.push({ -cost[i],i });
while (!pq.empty()) {
pair<double, int>cur = pq.top();
pq.pop();
if (cur.second != h && -cur.first == cost[cur.second]) {
for (auto& it : graph[cur.second]) {
double sum = cost[cur.second] + it.second;
if (sum < cost[it.first]) {
cost[it.first] = sum, pq.push({ -cost[it.first],it.first });
}
}
}
}
}
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) {
n = N, m = M, k = min(K, 70), h = H;
reset();
for (int i = 0; i < m; i++)
graph[x[i]].push_back({ y[i],c[i] }), graph[y[i]].push_back({ x[i],c[i] });
DFS1(0);
if (!vis[h])
return -1;
for (int i = 0; i <= n; i++)
cost[i] = oo, vis[i] = false;
vec.clear();
DFS2(0);
for (auto& it : vec)
if (!arr[it] || !it)
cost[it] = 0;
ret = double(oo);
for (int i = 0; i <= k; i++) {
Dijkstra();
ret = min(ret, cost[h]), cost[h] = oo;
for (int j = 0; j < n; j++)
copCost[j] = cost[j];
for (int j = 0; j < n; j++) {
if (arr[j] != 2)
continue;
double mn = oo;
for (auto& it : graph[j]) {
double sum = copCost[it.first] + it.second;
mn = min(mn, sum);
}
mn /= double(2);
cost[j] = min(cost[j], mn);
}
}
return ret;
}
