#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
struct kek {
double dist;
int node;
int cnt;
};
bool operator < (const kek &a, const kek &b) {
return a.dist < b.dist;
}
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; i++) {
g[x[i]].push_back({y[i], c[i]});
g[y[i]].push_back({x[i], c[i]});
}
priority_queue<kek> pq;
vector<vector<double>> dist(n, vector<double>(k + 1, 1e18));
for (int i = 0; i < n; i++) {
if (i == 0 || arr[i] == 0) {
dist[i][0] = 0;
pq.push({0, i, 0});
}
}
while (!pq.empty()) {
int u = pq.top().node;
int kk = pq.top().cnt;
pq.pop();
for (auto [v, c] : g[u]) {
if (dist[u][kk] + c < dist[v][kk]) {
dist[v][kk] = dist[u][kk] + c;
pq.push({dist[v][kk], v, kk});
}
if (v != h && arr[v] == 2 && kk + 1 < k && (dist[u][kk] + c) / 2 < dist[v][kk + 1]) {
dist[v][kk + 1] = (dist[u][kk] + c) / 2;
pq.push({dist[v][kk + 1], v, kk + 1});
}
}
}
double res = 1e18;
for (int i = 0; i <= k; i++) res = min(res, dist[h][i]);
return res;
}
