#define _CRT_SECURE_NO_WARNINGS
#include <cassert>
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll INF = 1e14;
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
vector < vector < pair < int, int > > > v(N);
for (int i = 0; i < M; i++) {
v[x[i]].push_back({ y[i], c[i] });
v[y[i]].push_back({ x[i], c[i] });
}
vector < bool > vis(N, false);
queue < int > bq;
bq.push(0);
while (!bq.empty()) {
int val = bq.front();
bq.pop();
if (vis[val]) continue;
vis[val] = true;
for (auto to : v[val]) {
if (!vis[to.first]) {
bq.push(to.first);
}
}
}
vector < vector < bool > > used(N, vector < bool >(K + 1, false));
vector < vector < ld > > F(N, vector < ld >(K + 1, (ld)INF));
using queueType = pair < ld, pair < int, int > >;
priority_queue < queueType, vector < queueType >, greater < queueType > > q;
F[0][0] = 0;
q.push({ 0, {0, 0} });
for (int i = 0; i < N; i++) {
if (arr[i] == 0 && vis[i]) {
F[i][0] = 0;
q.push({ F[i][0], {0, i} });
}
}
while (!q.empty()) {
int val = q.top().second.second;
int sp = q.top().second.first;
q.pop();
if (used[val][sp]) continue;
used[val][sp] = true;
if (val == H) continue;
for (auto e : v[val]) {
int to = e.first;
int w = e.second;
ld tmp = F[val][sp] + (ld)w;
if (tmp < F[to][sp]) {
F[to][sp] = tmp;
q.push({ tmp, {sp, to} });
}
if (arr[to] == 2 && sp + 1 <= K && tmp / 2 < F[to][sp + 1]) {
F[to][sp + 1] = tmp / 2;
q.push({ tmp / 2, {sp + 1, to} });
}
}
}
ld res = INF;
bool flag = false;
for (int i = 0; i <= K; i++) {
if (used[H][i]) flag = true;
if (F[H][i] < res) {
res = F[H][i];
}
}
if (!flag) {
return -1;
}
return res;
}
