#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()
const int INF = (int)1e18 + 18;
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, int H, vector <int> &A) {
for (auto [v, c] : adj[u]) if (v != p && v != H) {
if (A[v] == 0)
qu.push(v);
dfs1(v, u, H, 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 });
}
qu.push(0);
dfs1(0, -1, H, A);
dp = vector <long long> (N, 1e18);
while (sz(qu)) {
dp[qu.front()] = 0;
dfs2(qu.front(), -1);
qu.pop();
}
return dp[H];
}
}
namespace sub5 {
bool check_condition(int N, int M, int K, int H, vector <int> &A) {
return K <= 30 && count(all(A), 1) == N;
}
vector <vector <pair <int, int>>> adj;
vector <long long> d;
priority_queue <pair <long long, int>, vector <pair <long long, int>>, greater <pair <long long, int>>> pq;
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 });
}
d = vector <long long> (N, 1e18);
pq.push({ d[0] = 0, 0 });
while (sz(pq)) {
auto [du, u] = pq.top(); pq.pop();
if (d[u] != du)
continue;
for (auto [v, c] : adj[u])
if (d[v] > du + c)
pq.push({ d[v] = du + c, v });
}
return d[H] >= 1e18 ? -1 : d[H];
}
}
namespace sub6 {
bool check_condition(int N, int M, int K, int H, vector <int> &A) {
return K <= 30 && *max_element(all(A)) <= 1;
}
vector <vector <pair <int, int>>> adj;
vector <long long> d;
priority_queue <pair <long long, int>, vector <pair <long long, int>>, greater <pair <long long, int>>> pq;
vector <bool> vst;
void dfs(int u, int H, vector <int> &A) {
for (auto [v, c] : adj[u]) if (vst[v] == 0 && v != H) {
if (A[v] == 0)
pq.push({ d[v] = 0, v });
vst[v] = 1;
dfs(v, H, A);
}
}
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 });
}
d = vector <long long> (N, 1e18);
vst = vector <bool> (N, 0);
pq.push({ d[0] = 0, 0 });
dfs(0, H, A);
while (sz(pq)) {
auto [du, u] = pq.top(); pq.pop();
if (d[u] != du)
continue;
for (auto [v, c] : adj[u])
if (d[v] > du + c)
pq.push({ d[v] = du + c, v });
}
return d[H] >= 1e18 ? -1 : d[H];
}
}
namespace sub478 {
vector <vector <pair <int, int>>> adj;
vector <vector <double>> d;
priority_queue <tuple <double, int, int>, vector <tuple <double, int, int>>, greater <tuple <double, int, int>>> pq;
vector <bool> vst;
void dfs(int u, int H, vector <int> &A) {
for (auto [v, c] : adj[u]) if (vst[v] == 0 && v != H) {
if (A[v] == 0)
pq.push({ d[v][0] = 0, v, 0 });
vst[v] = 1;
dfs(v, H, A);
}
}
double solve(int N, int M, int K, int H, vector <int> &A, vector <EDGE> &edge) {
K = max(K, 70);
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 });
}
d = vector <vector <double>> (N, vector <double> (K + 1, 1e18));
vst = vector <bool> (N, 0);
pq.push({ d[0][0] = 0, 0, 0 });
dfs(0, H, A);
while (sz(pq)) {
auto [du, u, used] = pq.top(); pq.pop();
if (d[u][used] != du)
continue;
if (u == H)
continue;
for (auto [v, c] : adj[u]) {
if (d[v][used] > du + c)
pq.push({ d[v][used] = du + c, v, used });
if (A[v] == 2) if (used + 1 <= K) if (d[v][used + 1] > (du + c) / 2)
pq.push({ d[v][used + 1] = (du + c) / 2, v, used + 1 });
}
}
double ret = *min_element(all(d[H]));
return (ret >= 1e18 ? -1 : ret);
}
}
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);
// else if (sub5 :: check_condition(N, M, K, H, A))
// return sub5 :: solve(N, M, K, H, A, edge);
// else if (sub6 :: check_condition(N, M, K, H, A))
// return sub6 :: solve(N, M, K, H, A, edge);
// else
return sub478 :: solve(N, M, K, H, A, edge);
return -1;
}
#ifdef OP_DEBUG
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) << ".000000000000"<< '\n';
}
}
#endif
