#include<bits/stdc++.h>
using namespace std;
const double INF=1e18;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
k=min(k, 100);
vector<vector<pair<int, double>>> adj(n);
for(int i=0; i<m; i++) {
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
vector<double> dist(n), temp(n);
for(auto &p : dist) p=INF;
for(auto &p : temp) p=INF;
priority_queue<pair<double, int>> pq;
double ans=INF; temp[0]=0.;
for(int j=0; j<=k; j++) {
vector<double> temp(n); for(double &p : temp) p=INF;
if(j) {
for(int i=0; i<n; i++) {
if(a[i]==1 || dist[i]==INF) continue;
if(a[i]==0) temp[i]=0;
pq.push({-dist[i]/2., i});
}
} else pq.push({0., 0});
while(!pq.empty()) {
auto [cur, u]=pq.top(); cur=-cur;
pq.pop();
if(u==h) continue;
for(auto [v, w] : adj[u]) {
if(temp[v]>cur+w) {
if(a[v]==0) temp[v]=0.;
else temp[v]=cur+w;
pq.push({-temp[v], v});
}
}
}
ans=min(ans, temp[h]);
if(j==0 && temp[h]==INF) break;
swap(temp, dist);
}
return (ans<INF ? ans : -1.);
}
/*int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m, k, h; cin >> n >> m >> k >> h;
vector<int> x(m), y(m), c(m), a(n);
for(int &p : x) cin >> p;
for(int &p : y) cin >> p;
for(int &p : c) cin >> p;
for(int &p : a) cin >> p;
cout << solve(n, m, k, h, x, y, c, a) << '\n';
return 0;
}*/
