#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
const int maxn = 1e5 + 5;
int p[maxn];
int find(int u){
return (p[u] == u ? u : p[u] = find(p[u]));
}
bool minimize(double &a, double b){
if(a > b){
a = b;
return true;
}return false;
};
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a){
vector<vector<array<int, 2>>> g(n);
for(int i = 0; i < n; i++) p[i] = i;
for(int i = 0; i < m; i++){
if(x[i] != h && y[i] != h) p[find(x[i])] = find(y[i]);
g[x[i]].push_back({y[i], c[i]});
g[y[i]].push_back({x[i], c[i]});
}
k = min(k, 69);
vector<double> pwr(k + 1, 1);
for(int i = 1; i <= k; i++) pwr[i] = pwr[i - 1] / 2;
vector<vector<double>> dist(n, vector<double>(k + 1, 1e18));
priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> pq;
dist[h][k] = a[0] = 0;
pq.push({0, h, k});
while(pq.size()){
auto [d, u, j] = pq.top();
pq.pop();
if(dist[u][j] < d) continue;
if(a[u] == 0) return d;
for(auto [v, w]: g[u]){
if(find(v) != find(0)) continue;
if(minimize(dist[v][j], d + w * pwr[k - j])) pq.push({dist[v][j], v, j});
if(a[u] == 2 && j) if(minimize(dist[v][j - 1], d + w * pwr[k - j + 1])) pq.push({dist[v][j - 1], v, j - 1});
}
}
return -1;
}
