#include "cyberland.h"
#pragma GCC optimize("O3")
#pragma optimize("avx2")
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("curling.in", "r", stdin), freopen("curling.out", "w", stdout)
const __int128 INF = 2e18 + 7;
struct cmp{
bool operator()(pair<__int128, int> a, pair<__int128, int> b){
return a.st < b.st;
}
};
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
__int128 off = 1<<20;
int lim = min(K, 70);
vector<vector<__int128>> dist(lim + 5, vector<__int128>(N, INF * off));
vector<pii> adj[N + 5];
for (int i = 0; i < M; i++){
adj[x[i]].pb({y[i], c[i] * off});
adj[y[i]].pb({x[i], c[i] * off});
}
vector<int> mark(N + 5, 0);
queue<int> q;
q.push(0);
mark[0] = 1;
while(!q.empty()){
int top = q.front();
q.pop();
for (auto i : adj[top]){
if (mark[i.st] == 0){
mark[i.st] = 1;
if (i.st != H) q.push(i.st);
}
}
}
dist[0][H] = 0;
__int128 mini = INF;
for (int i = 0; i <= lim; i++){
priority_queue<pair<__int128, int>, vector<pair<__int128, int>>, cmp> q;
for (int j = 0; j < N; j++){
if (i == 0 || j != H) q.push({-dist[i][j], j});
}
__int128 pre1 = (1LL<<i), pre2 = (1LL<<(i + 1));
while(!q.empty()){
int top = q.top().nd;
q.pop();
int curr = i;
if (arr[top] != 2 || i == lim){
for (auto j : adj[top]){
int v = j.st, w = j.nd;
__int128 upd = dist[i][top] + w / pre1;
if (dist[i][v] > upd){
dist[i][v] = upd;
if (v != H) q.push({-upd, v});
}
}
}
else if (arr[top] == 2) {
for (auto j : adj[top]){
int v = j.st, w = j.nd;
__int128 upd = dist[i][top] + w / pre2;
if (dist[i + 1][v] > upd){
dist[i + 1][v] = upd;
}
}
}
}
for (int j = 0; j < N; j++){
if (mark[j] && arr[j] == 0) mini = min(mini, dist[i][j]);
}
mini = min(mini, dist[i][0]);
}
double ans = (double)mini / off;
if (ans > 1e18) return -1;
return ans;
}
