#include "cyberland.h"
#include <vector>
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define ll long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
const ll maxn = 2e5+10 , N = 1e5 +1 , maxq = 202 , inf = 1e18 , maxk = 2022 , mod =1e9+7 ;
ld dis[maxn][102] ;int mark[maxn];
vector <pair<int,ld> > G[maxn] ;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> t) {
rep(i , 0 ,m-1){
G[x[i]].pb({y[i] , c[i]});
G[y[i]].pb({x[i] , c[i]}) ;
}
k = min(k , 100);
rep(j , 0 , n-1)rep(z , 0 , k)dis[j][z] = inf ;
dis[h][0] = 0 ;
ld ans =inf;
rep(i , 0 , k){
priority_queue <pair<ld,int> > pq ;
rep(j , 0 , n-1){
pq.push({-dis[j][i] , j}) ;
mark[j] =0 ;
}
while(sz(pq)){
int v = pq.top().S ;pq.pop();
if(mark[v] == 1)continue;
mark[v] = 1;
for(auto a : G[v]){
if(dis[a.F][i] > dis[v][i]+a.S){
dis[a.F][i] = dis[v][i] + a.S ;
pq.push({-dis[a.F][i] , a.F});
}
}
}
rep(j , 0 , n-1){
rep(z ,0 , sz(G[j])-1){
G[j][z].S /= 2.0000000 ;
}
}
rep(j , 0 , n-1){
if(j == 0 || t[j] == 0)
ans = min(ans , dis[j][i]) ;
}
rep(j , 0 , n-1){
if(t[j]==2){
dis[j][i+1] = dis[j][i] ;
}
}
}
if(ans == inf)return -1 ;
return ans ;
}
