#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
const double EPS = 1e-6;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
vector adj(N, vector<pair<int, int>>());
for(int i = 0; i < M; i++)
{
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
vector dp(N, vector<long long>(K + 1, 1e15));
pqg<tuple<long long, int, int>> pq;
pq.push({0, 0, 0});
while(not pq.empty())
{
auto [cost, u, c] = pq.top();
pq.pop();
if(arr[u] == 0)
cost = 0;
if(u == H)
{
if(arr[u] == 2 and c < K)
cost /= 2;
if(dp[u][c] > cost)
dp[u][c] = cost;
continue;
}
if(dp[u][c] <= cost or llabs(dp[u][c] - cost) <= EPS)
continue;
dp[u][c] = cost;
for(auto [v, w]: adj[u])
{
pq.push({cost + w, v, c});
if(arr[u] == 2 and c + 1 <= K)
pq.push({cost / 2 + w, v, c + 1});
}
}
long long mn = 1e15;
for(int i = 0; i <= K; i++)
{
if(dp[H][i] < mn and llabs(mn - dp[H][i]) > EPS)
mn = dp[H][i];
}
if(mn >= 1e15 or llabs(1e15 - mn) <= EPS)
mn = -1;
return mn;
}
