#include "cyberland.h"
#include <bits/stdc++.h>
using i64 = long long;
using f64 = double;

template<typename Ta, typename Tb>
inline void chkmax(Ta &a, const Tb &b) {if (a < b)	a = b;}
template<typename Ta, typename Tb>
inline void chkmin(Ta &a, const Tb &b) {if (a > b)	a = b;}

constexpr int N = 1e5 + 10;
constexpr int M = 80;
constexpr f64 inf = 1e18;
constexpr f64 inf2 = 1e16;

f64 dis[M][N];
bool vis[M][N];
std::vector<std::array<int, 3>> G[M][N];
std::vector<int> G2[N];
bool vis2[N];
std::vector<int> zero;

struct node {
	int dep;
	f64 dis;
	int u;
	bool operator > (const node &b) const {
		return dep == b.dep ? dis > b.dis : dep > b.dep;
	}
};

f64 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) {
	for (int d = 0; d < M; d++)
		for (int i = 0; i < n; i++)
			G[d][i].clear();
	for (int i = 0; i < n; i++)
		G2[i].clear(), vis2[i] = false;
	zero.clear();

	chkmin(k, M - 1);

	auto add = [&](const int &dep, const int &u, const int &v, const int &w) {
		int t = (arr[v] == 2);
		if (dep + t < M)
			G[dep][u].push_back({dep + t, v, w});
	};

	for (int i = 0; i < m; i++) {
		G2[x[i]].push_back(y[i]);
		G2[y[i]].push_back(x[i]);
		for (int dep = 0; dep < M; dep++) {
			if (x[i] != h)
				add(dep, x[i], y[i], c[i]);
			if (y[i] != h)
				add(dep, y[i], x[i], c[i]);
		}
	}

	auto dfs = [&](auto self, int u) {
		if (vis2[u])
			return ;
		vis2[u] = true;
		if (u == 0 || arr[u] == 0)
			zero.push_back(u);
		if (u == h)
			return ;
		for (const int &v : G2[u]) {
			if (v == h)
				continue;
			self(self, v);
		}
	};
	if (arr[h] == 0)
		zero.push_back(h);
	dfs(dfs, 0);

	auto dijkstra = [&]() {
		for (int d = 0; d < M; d++)
			for (int i = 0; i < n; i++)
				dis[d][i] = inf, vis[d][i] = false;

		std::priority_queue<node, std::vector<node>, std::greater<node>> q;

		for (const int &u : zero) {
			dis[0][u] = 0;
			q.push({0, 0, u});
		}

		//		for (int d = 0; d < M; d++)
		//			dis[d][0] = 0, q.push({d, 0, 0});
		//		for (int u = 1; u < n; u++) {
		//			if (arr[u] == 0) {
		//				for (int d = 0; d < M; d++)
		//					dis[d][u] = 0, q.push({d, 0, u});
		//			}
		//		}

		while (!q.empty()) {
			auto [dep, d, u] = q.top();
			q.pop();
			if (vis[dep][u])
				continue;
			vis[dep][u] = true;
			for (const auto &[nxd, v, w] : G[dep][u]) {
				if (arr[v] == 0) {
					if (dis[nxd][v] > 0) {
						dis[nxd][v] = 0;
						q.push({nxd, 0, v});
					}
				} else {
					if (nxd != dep) {
						if (dis[nxd][v] > (dis[dep][u] + w) / 2) {
							dis[nxd][v] = (dis[dep][u] + w) / 2;
							q.push({nxd, dis[nxd][v], v});
						}
					} else {
						if (dis[nxd][v] > dis[dep][u] + w) {
							dis[nxd][v] = dis[dep][u] + w;
							q.push({nxd, dis[nxd][v], v});
						}
					}
				}
			}
		}
	};

	dijkstra();

	f64 ans = inf;

	for (int d = 0; d <= k; d++)
		chkmin(ans, dis[d][h]);

	if (ans >= inf)
		return -1;
	else
		return ans;
}