#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
double solve(int n, int m, int k, int h, vector<int> u, vector<int> v, vector<int> w, vector<int> arr){
vector<vector<pii>> adj(n);
for(int i = 0; i < n; ++i)
adj[u[i]].pb({v[i], w[i]}), adj[v[i]].pb({u[i], w[i]});
vector<bool> is(n, false);
is[0]=1;
queue<int> q;
q.push(0);
while(!q.empty()){
int x=q.front();
q.pop();
tr(it, adj[x])
if(!is[it->ff])
is[it->ff]=1, q.push(it->ff);
}
if(!is[h])
return -1;
using node=tuple<double, int, int>;
// distance, node, how many time I used operation dividing
priority_queue<node, vector<node>, greater<node>> pq;
vector<vector<double>> dis(n, vector<double> (k+2, 1e18));
for(int i = 0; i < n; ++i)
if(i==0 or arr[i]==0)
pq.push({0, i, 0}), dis[i][0]=0;
while(!pq.empty()){
double d;
int x, cnt;
tie(d, x, cnt)=pq.top();
pq.pop();
if(d!=dis[x][cnt])
continue;
if(x==h)
continue;
tr(it, adj[x]){
if(umin(dis[it->ff][cnt], d+it->ss))
pq.push({dis[it->ff][cnt], it->ff, cnt});
if(cnt<k and arr[it->ff]==2 and umin(dis[it->ff][cnt+1], (double)(d+it->ss)/2))
pq.push({dis[it->ff][cnt+1], it->ff, cnt+1});
}
}
double answer=*min_element(all(dis[h]));
return answer;
}
