#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 100005
using namespace std;
typedef pair<int, int> ii;
const int B = 100;
vector<ii> adj[maxn];
double kc[B+1][maxn];
template <class T> inline void cmin(T &x, T y) {if (x > y) x = y;}
void bfs(int x, vector<int> &temp) {
queue<int> q;
q.push(x);
temp[x] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto [v, w] : adj[u]) {
if (!temp[v]) {
temp[v] = 1;
q.push(v);
}
}
}
}
void dijkstra(int N, int K, vector<int> &arr) {
for (int i = 0; i < N; i++) kc[0][i] = LLONG_MAX / 2;
vector<int> temp(N, 0);
bfs(0, temp);
kc[0][0] = 0;
priority_queue<pair<double, int> , vector<pair<double, int> >, greater<pair<double, int> > > q;
q.push({0, 0});
for (int i = 0; i < N; i++) {
if (arr[i] == 0 && temp[i]) {
kc[0][i] = 0;
q.push({0, i});
}
}
while (!q.empty()) {
double D = q.top().fi;
int u = q.top().se; q.pop();
if (D > kc[0][u]) continue;
for (auto [v, w] : adj[u]) {
if (kc[0][v] > kc[0][u] + w) {
kc[0][v] = kc[0][u] + w;
q.push({kc[0][v], v});
}
}
}
for (int o = 1; o <= K; o++) {
for (int i = 0; i < N; i++) kc[o][i] = kc[o-1][i];
for (int i = 0; i < N; i++) {
if (arr[i] != 2) continue;
if (kc[o-1][i] >= LLONG_MAX/10) continue;
for (auto [j, w] : adj[i]) cmin(kc[o][j], kc[o-1][i]/2.0 + w);
}
for (int i = 0; i < N; i++) q.push({kc[o][i], i});
while (!q.empty()) {
double D = q.top().fi;
int u = q.top().se; q.pop();
if (D > kc[o][u]) continue;
for (auto [v, w] : adj[u]) {
if (kc[o][v] > kc[o][u] + w) {
kc[o][v] = kc[o][u] + w;
q.push({kc[o][v], v});
}
}
}
}
}
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++) {
if (y[i] != H) adj[y[i]].emplace_back(x[i], c[i]);
if (x[i] != H) adj[x[i]].emplace_back(y[i], c[i]);
}
K = min(K, B);
dijkstra(N, K, arr);
double ans = kc[K][H];
for (int i = 0; i < N; i++) adj[i].clear();
if (ans >= LLONG_MAX/10) return -1;
return ans;
}
