#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
#define f(i,a,b) for(int i = a; i < b; i++)
typedef pair <double, pair<int, int>> ii;
const int N = 1e5 + 5;
const double inf = 2e15;
int n, k;
double d[N][71];
bool vis[N];
vector <pair<int, double>> adj[N], adj_H;
vector <int> ARR;
void check(int u){
vis[u] = 1;
for(auto p: adj[u]){
int v = p.first;
if(!vis[v]) check(v);
}
}
void clear(){
adj_H.clear(); ARR.clear();
f(i,0,n) adj[i].clear(), vis[i] = 0;
}
void dij(){
priority_queue <ii, vector <ii>, greater <ii>> q;
f(i,1,n) {
f(j,0,k+1) d[i][j] = inf;
}
f(j,0,k+1){
d[0][j] = 0;
q.push({0, {j, 0}});
}
while(!q.empty()){
auto pa = q.top(); q.pop();
double d_u = pa.first; int u = pa.second.second; int c = pa.second.first;
if(d[u][c] != d_u) continue;
for(auto p: adj[u]){
int v = p.first; double w = p.second;
double new_ = 0;
if(ARR[v] != 0) new_ = d[u][c] + w;
if(d[v][c] > new_){
d[v][c] = new_;
q.push({d[v][c], {c, v}});
}
if(ARR[v] == 2 and c+1 <= k){
double val = (d[u][c] + w) / 2;
if(d[v][c+1] > val){
d[v][c+1] = val;
q.push({d[v][c+1], {c+1, v}});
}
}
}
}
}
double solve(int Ni, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
n = Ni;
ARR = arr;
k = min(70, K);
f(i,0,M){
if(x[i] == H or y[i] == H){
adj_H.push_back({x[i] + y[i] - H, c[i]});
}
else {
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
}
check(0);
dij();
double ans = inf;
for(auto p: adj_H) {
int v = p.first; double w = p.second;
if(vis[v]) f(i,0,k+1) ans = min(ans, d[v][i] + w);
}
clear();
return (ans == inf) ? -1 : ans;
}
