#include <bits/stdc++.h>
#define pb push_back
#define se second
#define fi first
using namespace std;
const int MAX_N = 1e5;
vector<vector<pair<int, int>>> adj;
double dijkstra(int n, int k, int h, vector<int>& arr) {
vector<vector<double>> dist(n, vector<double>(k+1, 1e9)); // mínima distància a i gastant j vegades
vector<double> dist2(n, 1e9);
priority_queue<pair<int, pair<int, int>>> pq;
dist[0][0] = 0;
pq.push({0, {0, 0}});
while (!pq.empty()) {
double d = -pq.top().fi;
int u = pq.top().se.fi;
int i = pq.top().se.se;
pq.pop();
if (dist[u][i] != d) continue;
if (u == h) continue;
for (auto v: adj[u]) {
if (!arr[v.fi]) {
dist[v.fi][i] = 0;
if (dist2[v.fi] > 0) {
dist2[v.fi] = 0;
pq.push({0, {v.fi, 0}});
}
} else {
if (dist[v.fi][i] > d+v.se) {
dist[v.fi][i] = d+v.se;
pq.push({-dist[v.fi][i], {v.fi, i}});
}
if (arr[v.fi] == 2 && i+1 <= k) {
if (dist[v.fi][i+1] > (double)(d+v.se)/2) {
dist[v.fi][i+1] = (double)(d+v.se)/2;
pq.push({-dist[v.fi][i+1], {v.fi, i+1}});
}
}
}
}
}
double ans = 1e9;
for (int i = 0; i <= k; ++i) ans = min(ans, dist[h][i]);
return ans;
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
adj = vector<vector<pair<int, int>>>(N);
for (int i = 0; i < M; ++i) {
adj[x[i]].pb({y[i], c[i]});
adj[y[i]].pb({x[i], c[i]});
}
return dijkstra(N, K, H, arr);
}
