#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
using namespace std;
const int N = 1e5 + 10;
double dis[N][88]; bool vis[N][88];
vector<pair<int, int> > z[N];
double solve(signed n, signed m, signed k, signed h, std::vector<signed> x, std::vector<signed> y, std::vector<signed> c, std::vector<signed> arr) {
	h++;
	k = min(k, 85);
	for (int i = 1; i <= n; i++) {
		z[i].clear();
	}
	for (int i = 0; i < m; i++) {
		int u = x[i], v = y[i], w = c[i];
		u++, v++;
		z[u].push_back({v, w}), z[v].push_back({u, w});
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < k; j++) {
			dis[i][j] = 1e9;
		}
	}
	queue<pair<int, int> > q; q.push({1, 0}); dis[1][0] = 0; vis[1][0] = false;
	while (q.size()) {
		pair<int, int> f = q.front(); q.pop(); vis[1][0] = false;
		for (int i = 0; i < z[f.x].size(); i++) {
			int g = z[f.x][i].first, w = z[f.x][i].second;
			if (arr[g - 1] == 1) {
				if (dis[g][f.y] > dis[f.x][f.y] + w) {
					dis[g][f.y] = dis[f.x][f.y] + w;
					if (!vis[g][f.y]){
						q.push({g, f.y});
						vis[g][f.y] = true;
					}
				}
			} else if (arr[g - 1] == 0) {
				dis[g][f.y] = 0;
				if (!vis[g][f.y]) {
					q.push({g, f.y});
					vis[g][f.y] = true;
				}
			} else {
				if (dis[g][f.y] > dis[f.x][f.y] + w) {
					dis[g][f.y] = dis[f.x][f.y] + w;
					if (!vis[g][f.y]) {
						q.push({g, f.y});
						vis[g][f.y] = true;
					}
				}
				if (f.y != k - 1 && dis[g][f.y + 1] > (dis[f.x][f.y] + w) / 2.) {
					dis[g][f.y + 1] = (dis[f.x][f.y] + w) / 2.;
					if (!vis[g][f.y + 1]) {
						q.push({g, f.y + 1});
						vis[g][f.y + 1] = true;
					}
				}
			}
		}
	}
	double mx = 1e9;
	for (int i = 0; i < k; i++) {
		mx = min(mx, dis[h][i]);
	}
	if (mx < 1e-8) {
		mx = 0;
	}
	return mx;
}
signed main() {
	cout << solve(4, 4, 99990, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 3, 0, 4}, {1, 2, 0, 1}) << '\n';
	return 0;
}