/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA_RedSea"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
/// #define endl '\n'
using ll = long long;
using ld = long double;
using ull = unsigned long long;
const ll mod = 1000000007;
const ll mod1 = 998244353;
vector <int> dx = {0,0,-1,1},dy = {-1,1,0,0};
vector <char> dir = {'L','R','U','D'};
#include <cyberland.h>
vector <vector <vector <int>>> a;
vector <map <int,int>> v;
vector <int> ac,vis;
int c;
int calc1(int i){
if(i == c)return 1;
if(vis[i])return 0;
vis[i]++;
for(auto& j : a[i]){
if(calc1(j[0]))return 1;
}
return 0;
}
double calc(int i,int k,double time){
if(i == c)return time;
double r = LLONG_MAX;
for(auto& j : a[i]){
if(v[j[0]][time])continue;
v[j[0]][time]++;
time += j[1];
if(ac[j[0]] == 0)time = 0.0000000000;
else if(ac[j[0]] == 2){
if(k > 0)r = min(r,calc(j[0],k - 1,time / 2));
}
r = min(r,calc(j[0],k,time));
}
return r;
}
double solve(int N,int M,int K,int C,vector <int> U,vector <int> V,vector <int> T,vector <int> A){
c = C;
a.resize(N);
for(int i = 0;i < M;i++){
a[U[i]].push_back({V[i],T[i]});
a[V[i]].push_back({U[i],T[i]});
}
ac = A;
vis = vector <int> (N,0);
if(calc1(0) == 0)return -1.00000000000;
v.resize(N);
return calc(0,K,0);
}
/*
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
/// cout << fixed << setprecision(0);
/// cout.tie(0);
/// freopen("test.in", "r", stdin);
/// freopen("test.out", "w", stdout);
/// #undef endl
;
return 0;
}
*/
