#ifndef Nhoksocqt1
#include "cyberland.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<double, int> pdi;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 100005;
vector<ii> adj[MAXN];
double dist[31][MAXN];
int cityType[MAXN], numNode, numType0, cyberCity;
double solve(int _N, int _M, int _K, int _H, vector<int> _X, vector<int> _Y, vector<int> _C, vector<int> _A) {
numNode = _N, numType0 = _K, cyberCity = _H;
for (int i = 0; i < numNode; ++i)
adj[i].clear();
for (int i = 0; i < _M; ++i) {
int u(_X[i]), v(_Y[i]), w(_C[i]);
adj[u].push_back(ii(v, w));
adj[v].push_back(ii(u, w));
}
for (int i = 0; i < numNode; ++i)
cityType[i] = _A[i];
for (int j = 0; j <= numType0; ++j) {
for (int i = 0; i < numNode; ++i)
dist[j][i] = 1e18;
}
dist[0][0] = 0;
for (int k = 0; k <= numType0; ++k) {
priority_queue<pdi, vector<pdi>, greater<pdi>> heap;
for (int i = 0; i < numNode; ++i) {
if(dist[k][i] < ll(1e18))
heap.push({dist[k][i], i});
}
while(sz(heap)) {
double dis(heap.top().fi);
int u(heap.top().se);
heap.pop();
if(u == cyberCity || dis != dist[k][u])
continue;
for (int it = 0; it < sz(adj[u]); ++it) {
int v(adj[u][it].fi), w(adj[u][it].se);
if(cityType[v] > 0) {
if(dist[k][v] > dist[k][u] + w) {
dist[k][v] = dist[k][u] + w;
heap.push({dist[k][v], v});
}
if(cityType[v] == 2 && k < numType0)
dist[k + 1][v] = min(dist[k + 1][v], (dist[k][u] + w) / 2.0);
} else
if(dist[k][v] > 0) {
dist[k][v] = 0;
heap.push({dist[k][v], v});
}
}
}
}
double res(1e18);
for (int k = 0; k <= numType0; ++k)
res = min(res, dist[k][cyberCity]);
return (res >= 1e18) ? -1 : res;
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "cyberland"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
vector<int> _X, _Y, _C, _A;
int _N, _M, _K, _H;
cin >> _N >> _M >> _K >> _H;
_X.resize(_M);
_Y.resize(_M);
_C.resize(_M);
for (int i = 0; i < _M; ++i)
cin >> _X[i] >> _Y[i] >> _C[i];
_A.resize(_N);
for (int i = 0; i < _N; ++i)
cin >> _A[i];
double ans = solve(_N, _M, _K, _H, _X, _Y, _C, _A);
cout << setprecision(6) << fixed;
cout << "ANSWER: " << ans << '\n';
return 0;
}
#endif // Nhoksocqt1
