#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//set.find_by_order(x) x-position value
//set.order_of_key(x) number of strictly less elements don't need *set.??
#define N 100005
#define wr cout << "Continue debugging\n";
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <double, int>
#define pb push_back
#define ff first
#define ss second
int vis[N];
set<pii> q[N];
vector<pair<int,int>> E[N];
vector<int> z;
void dfs(int nd, int h){
vis[nd] = 1;
for (auto i : E[nd]){
if (i.ff == h or vis[i.ff]) continue;
dfs(i.ff, h);
}
}
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
for (int i = 0; i < max(70,n); i++){
vis[i] = 0;
E[i].clear();
if (i <= 70) q[i].clear();
}
for (int i = 0; i < m; i++){
E[x[i]].pb({y[i], c[i]});
E[y[i]].pb({x[i], c[i]});
}
z.clear();
z.pb(0);
vector<vector<double>> dis(min(73,k+2), vector<double>(n+1, 1e15));
dfs(0, h);
for (int i = 0; i < n; i++) if (!arr[i] and vis[i]) z.pb(i);
double ans = 1e15;
for (auto i : z){
dis[0][i] = 0;
q[0].insert({0, i});
}
for (int i = 0; i <= min(k,70); i++){
while(!q[i].empty()){
int x = (*q[i].begin()).ss;
q[i].erase(q[i].begin());
if (x == h) continue;
for (auto j : E[x]){
double res = dis[i][x]+j.ss;
if (dis[i][j.ff] > res){
dis[i][j.ff] = res;
q[i].insert({dis[i][j.ff], j.ff});
}
if (arr[j.ff] == 2){
res /= 2;
if (dis[i+1][j.ff] > res){
dis[i+1][j.ff] = res;
q[i+1].insert({dis[i+1][j.ff], j.ff});
}
}
}
}
ans = min(ans, dis[i][h]);
}
if (ans == 1e15) return double(-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 (int i = 0; i < m; i++){
// cin >> x[i] >> y[i] >> c[i];
// }
// for (int i = 0; i < n; i++) cin >> arr[i];
// cout << solve(n,m,k,h,x,y,c,arr);
// }
