/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double inf = 1e18;
const double err = 1e-7;
struct w{
int b,c;
};
w hi;
int n,m,k,h;
vector <int> a,v;
vector <double> d;
vector <vector <w>> g;
bool check(int i){
v[i] = 1;
for(auto& j : g[i]){
if(v[j.b])continue;
if(j.b == h || check(j.b))return 1;
}
return 0;
}
void calc(int i,int ck){
for(auto& j : g[i]){
if(a[j.b] == 0){
if(d[j.b] <= err)continue;
d[j.b] = 0.00000000000;
if(j.b != h)calc(j.b,ck);
}
else{
if(a[j.b] == 2 && ck < k){
if(d[j.b] - ((d[i] + j.c) / 2.0000000) > err){
d[j.b] = ((d[i] + j.c) / 2.00000000);
if(j.b != h)calc(j.b,ck + 1);
}
}
if((d[j.b] - (d[i] + j.c)) <= err)continue;
d[j.b] = (d[i] + j.c);
if(j.b != h)calc(j.b,ck);
}
}
}
double solve(int N,int M,int K,int H,vector <int> X,vector <int> Y,vector <int> C,vector <int> A){
n = N;m = M;k = K;h = H;a = A;
g.resize(n + 5);
for(int i = 0;i < m;i++){
hi.b = Y[i];
hi.c = C[i];
g[X[i]].push_back(hi);
hi.b = X[i];
g[Y[i]].push_back(hi);
}
v = vector <int> (n + 5,0);
if(check(0) == 0)return -1;
d = vector <double> (n + 5,inf);
d[0] = 0;
calc(0,0);
return d[h];
}
