#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
#include "cyberland.h"
#endif
using namespace std;
// #define int long long
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
struct EDGE {
int x, y, c;
};
void minimize(double &ret, double val) {
if (ret < -0.5)
ret = val;
ret = min(ret, val);
}
namespace sub1 {
bool check_condition(int N, int M, int K, int H, vector <int> &A) {
return N <= 3 && K <= 30;
}
double solve(int N, int M, int K, int H, vector <int> &A, vector <EDGE> &edge) {
if (H == 0)
return 0.0;
vector <vector <double>> cost(N, vector <double> (N, -1));
for (auto [u, v, c] : edge)
cost[u][v] = cost[v][u] = c;
if (N == 2)
return (cost[0][H] >= 0 ? cost[0][H] : -1);
double ret = (cost[0][H] >= 0 ? cost[0][H] : -1);
int other = 3 - H;
if (cost[0][other] >= 0 && cost[other][H] >= 0) {
if (A[other] == 0)
minimize(ret, cost[other][H]);
else if (A[other] == 1)
minimize(ret, cost[0][other] + cost[other][H]);
else {
if (K >= 1)
minimize(ret, cost[0][other] / 2.0 + cost[other][H]);
else
minimize(ret, cost[0][other] + cost[other][H]);
}
}
return ret;
}
}
namespace sub2 {
bool check_condition(int N, int M, int K, int H, vector <int> &A) {
return M == N - 1 && K <= 30 && count(all(A), 1) == N;
}
vector <vector <pair <int, int>>> adj;
vector <long long> dp;
void dfs(int u, int p) {
for (auto [v, c] : adj[u]) if (v != p) {
dp[v] = dp[u] + c;
dfs(v, u);
}
}
double solve(int N, int M, int K, int H, vector <int> &A, vector <EDGE> &edge) {
adj = vector <vector <pair <int, int>>> (N, vector <pair <int, int>> ());
for (auto [u, v, c] : edge) {
adj[u].push_back({ v, c });
adj[v].push_back({ u, c });
}
dp = vector <long long> (N, 0ll);
dfs(0, -1);
return dp[H];
}
}
namespace sub3 {
bool check_condition(int N, int M, int K, int H, vector <int> &A) {
return M == N - 1 && K <= 30 && *max_element(all(A)) <= 1;
}
vector <vector <pair <int, int>>> adj;
vector <long long> dp;
queue <int> qu;
void dfs1(int u, int p, vector <int> &A) {
for (auto [v, c] : adj[u]) if (v != p) {
if (A[v] == 0)
qu.push(v);
dfs1(v, u, A);
}
}
void dfs2(int u, int p) {
for (auto [v, c] : adj[u]) if (v != p) {
dp[v] = min(dp[v], dp[u] + c);
dfs2(v, u);
}
}
double solve(int N, int M, int K, int H, vector <int> &A, vector <EDGE> &edge) {
adj = vector <vector <pair <int, int>>> (N, vector <pair <int, int>> ());
for (auto [u, v, c] : edge) {
adj[u].push_back({ v, c });
adj[v].push_back({ u, c });
}
dfs1(0, -1, A);
if (A[0] == 0)
qu.push(0);
dp = vector <long long> (N, 1e18);
while (sz(qu)) {
dp[qu.front()] = 0;
dfs2(qu.front(), -1);
qu.pop();
}
return dp[H];
}
}
double solve(int N, int M, int K, int H, vector <int> X, vector <int> Y, vector <int> C, vector <int> A) {
vector <EDGE> edge;
for (int i = 0; i < M; ++i)
edge.push_back({ X[i], Y[i], C[i] });
if (sub1 :: check_condition(N, M, K, H, A))
return sub1 :: solve(N, M, K, H, A, edge);
else if (sub2 :: check_condition(N, M, K, H, A))
return sub2 :: solve(N, M, K, H, A, edge);
else if (sub3 :: check_condition(N, M, K, H, A))
return sub3 :: solve(N, M, K, H, A, edge);
return -1;
}
// main() {
// int T; cin >> T;
// while (T--) {
// int N, M, K, H; cin >> N >> M >> K >> H;
// vector <int> A(N);
// for (int &a : A)
// cin >> a;
// vector <int> X(M), Y(M), C(M);
// for (int i = 0; i < M; ++i)
// cin >> X[i] >> Y[i] >> C[i];
// cout << (long long)solve(N, M, K, H, X, Y, C, A) << '\n';
// }
// }
