#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <random>
#include <queue>
#include <numeric>
#include <array>
#include <iomanip>
#include <stack>
#include <chrono>
#include <climits>
#include <bitset>
using namespace std;
using ll = int;
using ld = long double;
using vd = vector<ld>;
using vi = vector<ll>;
using vii = vector<vi>;
using viii = vector<vii>;
using pi = pair<ll, ll>;
using vpi = vector<pi>;
using vb = vector<bool>;
using vs = vector<string>;
#define vec vector
#define cmax(x, ...) x = max({x, __VA_ARGS__})
#define cmin(x, ...) x = min({x, __VA_ARGS__})
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const ll N = 5e5 + 5, MOD = 1e9 + 7, K = 20;
ld INF = 1e18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<vpi> g(n);
cmin(k, 70);
for (ll i = 0; i < m; i++) {
g[x[i]].push_back({ y[i], c[i] });
g[y[i]].push_back({ x[i], c[i] });
}
vb reach(n, false);
auto check = [&](auto&& check, ll v) -> void {
reach[v] = true;
if (v == h) return;
for (auto& [x, y] : g[v]) {
if (reach[x]) continue;
check(check, x);
}
};
check(check, 0);
if (!reach[h]) return -1;
vd dp(n, INF); for (ll i = 0; i < n; i++) {
if (reach[i] && (i == 0 || arr[i] == 0)) dp[i] = 0;
}
ld ans = INF;
for (ll i = 0; i <= k; i++) {
priority_queue<pair<ld, int>, vector<pair<ld, int>>, greater<>> pq;
for (ll j = 0; j < n; j++) {
if (dp[j] != INF) pq.push({dp[j], j});
}
while (!pq.empty()) {
auto [w, v] = pq.top(); pq.pop();
if (v == h) continue;
for (auto& [x, y] : g[v]) {
if (w + y > dp[x]) continue;
cmin(dp[x], w + y);
pq.push({ w + y, x});
}
}
cmin(ans, dp[h]);
vd ndp(n, INF);
bool done = false;
for (ll j = 0; j < n; j++) {
if (dp[j] == INF || j == h) continue;
for (auto& [x, y] : g[j]) {
if (arr[x] != 2 || ndp[x] < (dp[j] + y) / 2) continue;
cmin(ndp[x], (dp[j] + y) / 2);
done = true;
}
}
for (ll j = 0; j < n; j++) cmin(dp[j], ndp[j]);
if (!done) break;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
long long tt = 1;
//cin >> tt;
while (tt--) {
solve(4, 4, 30, 3, { 0, 0, 1, 2 }, { 1, 2, 3, 3 }, { 5, 4, 2, 4 }, { 1, 0, 2, 1 });
cout << '\n';
}
return 0;
}
/*
Можно начинать от 0 а также городов которые обнуляют. А вот что делать с делением хзшка
Какие темы повторить:
1) мст
2) 2сат
3) точки артикуляции
4) ксор базис
5) эйлеровый цикл, путь
6) кмп
7) конвекс хулл
8) вафельное дерево
9) суфиксный массив
10) суффиксный автомат
11) ним
*/
