#include <bits/stdc++.h>
using namespace std;
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
const int NM = 1e5, KM = 30;
const double inf = 1e18;
int N, M, K, H;
vector <pii> adj[NM+5];
vector <int> arr;
double d[NM+5][KM+5][2];
priority_queue <pair <double, pii>, vector <pair <double, pii> >, greater <pair <double, pii> > > pq;
double ans;
void dijkstra(){
for (int t = 0; t <= K; t++){
while (!pq.empty()) pq.pop();
for (int i = 0; i < N; i++){
if (t == 0){
if (i == 0) d[i][t][0] = 0, d[i][t][1] = +inf;
else d[i][t][0] = d[i][t][1] = +inf;
}
else{
if (arr[i] == 2){
d[i][t][0] = d[i][t-1][0];
d[i][t][1] = min(d[i][t-1][1], d[i][t-1][0]*0.5);
}
else{
d[i][t][0] = d[i][t-1][0];
d[i][t][1] = +inf;
}
if (i == H) d[i][t][0] = d[i][t][1] = +inf;
}
}
while (!pq.empty()) pq.pop();
for (int i = 0; i < N; i++)
for (int j = 0; j < 2; j++)
pq.push(mp(d[i][t][j], mp(i, j)));
while (!pq.empty()){
int u = pq.top().se.fi, j = pq.top().se.se;
if (d[u][t][j] != pq.top().fi){
pq.pop();
continue;
}
pq.pop();
for (pii _ : adj[u]){
int v = _.fi, c = _.se;
double tmp = d[u][t][j]+(double)c;
if (arr[v] == 0) tmp = 0;
if (tmp < d[v][t][0]){
d[v][t][0] = d[u][t][j]+(double)c;
pq.push(mp(d[v][t][0], mp(v, 0)));
}
}
}
ans = min(ans, d[H][t][0]);
}
}
double solve(int _N, int _M, int _K, int _H, vector <int> x, vector <int> y, vector <int> c, vector <int> _arr){
N = _N, M = _M, K = _K, H = _H;
for (int i = 0; i < N; i++) adj[i].clear();
for (int i = 0; i < M; i++){
adj[x[i]].push_back(mp(y[i], c[i]));
adj[y[i]].push_back(mp(x[i], c[i]));
}
arr = _arr;
ans = +inf;
dijkstra();
if (ans == +inf) ans = -1;
return ans;
}
