#include "cyberland.h"
// xiao fen tu hao shuai
#include<bits/stdc++.h>
using namespace std;

#define ll long long
// #define int long long
#define vi vector<int>
#define PB emplace_back
#define siz(a) ((int) (a.size()))
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
void print(vi &n) {rep(i, 0, siz(n) - 1) cout << n[i] << ' '; cout << endl;}

const int N = 1e5;
int a, b, c, d, q[N + 5];
bool vis[N + 5];
struct pii {
	int x;
	double y;
	bool operator<(const pii &o) const {return y > o.y;}
};
vector<pii> st[N + 5];
double dis[N + 5][76], f[N + 5];
void dfs(int n) {
	vis[n] = 1;
	if(n == d) return;
	for(pii x : st[n]) if(!vis[x.x]) dfs(x.x);
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> w, std::vector<int> arr) {
	a = N, b = M, c = K, d = H + 1;
	rep(i, 1, a) rep(j, 0, 75) dis[i][j] = 1e30;
	rep(i, 1, a) st[i].clear();
	rep(i, 0, b - 1) {
		st[x[i] + 1].PB((pii) {y[i] + 1, (double) w[i]});
		st[y[i] + 1].PB((pii) {x[i] + 1, (double) w[i]});
	}
	rep(i, 1, a) vis[i] = 0;
	dfs(1);
	if(!vis[d]) return -1;
	bool is = 0;
	rep(i, 0, a - 1) q[i + 1] = arr[i], is |= arr[i] == 2;
	c = min(c, 75);
	if(!is) c = 0;
	rep(i, 1, a) if(i == 1 || (vis[i] && q[i] == 0)) dis[i][0] = 0;
	rep(i, 0, c - 1) {
		priority_queue<pii> qu;
		rep(j, 1, a) {
			f[j] = dis[j][i];
			if(f[j] <= 1e20) qu.push((pii) {j, f[j]});
		}
		while(siz(qu)) {
			int u = qu.top().x;
			double w = qu.top().y;
			qu.pop();
			if(w != f[u] || u == d) continue;
			for(pii &x : st[u]) {
				int v = x.x;
				if(q[v] == 2) dis[v][i + 1] = min(dis[v][i + 1], (w + x.y) / 2);
				if(f[v] > x.y + w) {
					f[v] = x.y + w;
					if(v != d) qu.push((pii) {v, f[v]});
				}
			}
		}
		rep(j, 1, a) dis[j][i] = f[j];
	}
	priority_queue<pii> qu;
	rep(j, 1, a) if(j != d) {
		f[j] = dis[j][c];
		if(f[j] <= 1e20) qu.push((pii) {j, f[j]});
	}
	f[d] = 1e30;
	while(siz(qu)) {
		int u = qu.top().x;
		double w = qu.top().y;
		qu.pop();
		if(w != f[u]) continue;
		for(pii &x : st[u]) {
			int v = x.x;
			if(f[v] > x.y + w) {
				f[v] = x.y + w;
				qu.push((pii) {v, f[v]});
			}
		}
	}
	rep(j, 1, a) dis[j][c] = f[j];
	if(!vis[d]) return -1;
	double ans = 1e30;
	rep(i, 0, c) ans = min(ans, dis[d][i]);
	return ans;
}

// int main() {
// 	freopen("sample-1.in", "r", stdin);
//   int T;
//   assert(1 == scanf("%d", &T));
//   while (T--){
//     int N,M,K,H;
//     assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
//     std::vector<int> x(M);
//     std::vector<int> y(M);
//     std::vector<int> c(M);
//     std::vector<int> arr(N);
//     for (int i=0;i<N;i++)
//       assert(1 == scanf("%d", &arr[i]));
//     for (int i=0;i<M;i++)
//       assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
//     printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
//   }
// }