#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'
#include "cyberland.h"
// #include "stub.cpp"
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> a) {
vector<vector<ar<int, 2>>> adj(n);
for(int i = 0; i < m; i++) {
adj[x[i]].pb({y[i], c[i]});
adj[y[i]].pb({x[i], c[i]});
}
if(n <= 3 && k <= 30) {
double ans = 1e18;
int timer = 0;
auto dfs = [&](auto &&self, int v, int cnt, double cost) {
if(v == h) {
ans = min(ans, cost);
return;
}
if(timer > 1e3) {
return;
}
timer++;
for(auto [to, w] : adj[v]) {
double ncost = cost + w, ncnt = cnt;
if(a[to] == 0) ncost = 0;
if(a[to] == 2 && ncnt + 1 <= k) ncost /= 2, ncnt++;
self(self, to, ncnt, ncost);
self(self, to, cnt, cost + w);
}
};
dfs(dfs, 0, 0, 0);
return (ans == 1e18 ? -1 : ans);
}
vector<long long> d(n, 1e18);
d[0] = 0;
priority_queue<ar<long long, 2>, vector<ar<long long, 2>>, greater<>> pq;
pq.push({0, 0});
{
vector<int> used(n);
used[0] = 1;
queue<int> q;
q.push(0);
while(!q.empty()) {
auto v = q.front();
q.pop();
if(v == h) continue;
if(a[v] == 0) {
d[v] = 0;
pq.push({0, v});
}
for(auto [to, w] : adj[v]) {
if(!used[to]) {
used[to] = 1;
q.push(to);
}
}
}
}
while(!pq.empty()) {
auto [d_v, v] = pq.top();
pq.pop();
if(d_v != d[v]) continue;
for(auto [to, w] : adj[v]) {
if(d[to] > d[v] + w) {
d[to] = d[v] + w;
pq.push({d[to], to});
}
}
}
if(d[h] == 1e18) d[h] = -1;
return d[h];
}
