#include "cyberland.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define pii tuple<long double, ll, ll>
#define in(v) for(auto &elem:v){ cin>>elem; }
#define out(v) for(auto elem:v){ cout<<elem<<" "; } cout<<endl;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
typedef tree<pii, null_type, std::greater<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> cc, vector<int> arr) {
vector<vector<pair<ll, ll>>> adj(n);
for(ll i = 0; i<m; i++){
int u = x[i], v = y[i], c = cc[i];
adj[u].pb({c, v});
adj[v].pb({c, u});
}
vector<bool> vis(n, 0);
queue<ll> q;
q.push(0);
vis[0] = 1;
while(!q.empty()){
ll u = q.front();
q.pop();
if(u == h) continue;
for (auto [t, v]:adj[u]){
if(v == h) continue;
if(!vis[v]){
q.push(v);
vis[v] = 1;
}
}
}
const ll inf = 4e18;
//out(vis)
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<vector<long double>> dist(n, vector<long double> (k+1, inf));
for(ll i = 0; i<n; i++){
if (arr[i] == 0 && vis[i]){
pq.push({0, i, 0});
dist[i][0] = 0;
}
}
pq.push({0, 0, 0});
dist[0][0] = 0;
while(!pq.empty()){
auto [c, u, op] = pq.top();
pq.pop();
if(c > dist[u][op]){
continue;
}
for(auto [c, v]:adj[u]){
if(dist[v][op] > dist[u][op] + c){
dist[v][op] = dist[u][op]+c;
pq.push({dist[v][op], v, op});
}
if(op < k && dist[v][op+1] > dist[u][op]/2 + c){
dist[v][op+1] = dist[u][op]/2+c;;
pq.push({dist[v][op+1], v, op+1});
}
}
}
//out(dist);
long double ans = inf;
for(ll i = 0; i<=k; i++){
if(dist[h][i] <= ans){
ans = dist[h][i];
}
}
if(ans >= 3e18){
return -1;
}
return ans;
}
/*int main(){
int n, m, k, h;
cin>>n>>m>>k>>h;
vector<int> x(m), y(m), c(m), arr(n);
for(ll i = 0; i<m; i++){
cin>>x[i]>>y[i]>>c[i];
}
for(ll i = 0; i<n; i++){
cin>>arr[i];
}
cout<<solve(n, m, k, h, x, y, c, arr);
}*/
