#include "cyberland.h"
#include "bits/stdc++.h"
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
using namespace std;
const int N = 1e5 + 5;
vector<pair<int, int>> g[N];
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
for(int i = 0;i<M;++i){
g[x[i]].pb({c[i], y[i]});
g[y[i]].pb({c[i], x[i]});
}
K = min(K, 70);
priority_queue<array<double, 3>, vector<array<double, 3>>, greater<array<double, 3>>> pq;
const double INF = 1e18;
vector<vector<double>> dp(N, vector<double>(K + 1, INF));
vector<int> vis(N, 0);
queue<int> q;
q.push(0);
vector<int> start = {0};
while(!q.empty()){
int nd = q.front();
q.pop();
vis[nd] = 1;
for(auto it:g[nd]){
if(!vis[it.ss]){
if(it.ss == H) {vis[H] = 1; continue;}
vis[it.ss] = 1;
if(arr[it.ss] == 0) start.pb(it.ss);
q.push(it.ss);
}
}
}
for(auto nd:start){
for(int i = 0;i<=K;++i) dp[nd][i] = 0;
pq.push({0, (double)nd, 0});
}
while(!pq.empty()){
auto [cost, xx, k] = pq.top(); pq.pop();
int x = xx;
if(dp[x][k] != cost or x == H) continue;
for(auto [val, y]:g[x]){
if(arr[y] == 2){
double req1 = cost + val;
double req2 = (cost + val) / 2;
if(dp[y][k] > req1){
dp[y][k] = req1;
pq.push({req1, (double)y, k});
}
if(k + 1 <= K and dp[y][k + 1] > req2){
dp[y][k + 1] = req2;
pq.push({req2, (double)y, k + 1});
}
}
else if(arr[y]){
double req = cost + val;
if(dp[y][k] > req){
dp[y][k] = req;
pq.push({req, (double)y, k});
}
}
}
}
double ans = INF;
for(int i = 0;i<=K;++i) ans = min(ans, dp[H][i]);
for(int i = 0;i<N;++i){
g[i].clear();
}
if(ans >= INF) ans = -1;
return ans;
}
/*
1
3 2 30
2
1 2 1
1 2 12
2 0 4
1
4 4 30
3
1 0 2 1
0 1 5
0 2 4
1 3 2
2 3 4
*/
