#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
// subtask 1
// double ac(double k, double f)
// {
// // cout << k << " " << f;
// if (f == 0)
// {
// return 0;
// }
// else if (f == 2)
// {
// return k / 2;
// }
// else
// {
// return k;
// }
// };
// int _(int k)
// {
// return k == 2 ? 1 : 2;
// }
// 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> arr)
// {
// double MAX = (5.0e10 + 0.1);
// vector<vector<double>> C(3, vector<double>(3, MAX));
// vector<vector<bool>> V(3, vector<bool>(3, false));
// for (int i = 0; i < M; i++)
// {
// C[x[i]][y[i]] = min(C[x[i]][y[i]], (double)c[i]);
// C[y[i]][x[i]] = min(C[y[i]][x[i]], (double)c[i]);
// V[x[i]][y[i]] = true;
// V[y[i]][x[i]] = true;
// }
// if ((!V[0][H] && !V[0][_(H)]) || (!V[0][H] && !V[H][_(H)]))
// {
// return -1;
// }
// // cout << C[0][2] << " ___" << "\n";
// return min(ac(C[0][_(H)], arr[_(H)]) + C[_(H)][H], C[0][H]);
// }
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> arr)
{
vector<vector<pair<int, double>>> adj(N);
vector<double> cost(N, 5.0e17);
vector<bool> visited(N, false);
double minCost = 5.0e17;
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]});
}
priority_queue<pair<double, int>> pq;
cost[H] = 0;
pq.push({0.0, H});
// cout << pq.top().first << " \n";
while (!pq.empty())
{
double cst = -pq.top().first;
int node = pq.top().second;
pq.pop();
visited[node] = true;
if (arr[node] == 0)
{
minCost = min(minCost, cost[node]);
}
for (int i = 0; i < adj[node].size(); i++)
{
int v = adj[node][i].first;
double w = adj[node][i].second;
if (cost[v] > cost[node] + w)
{
cost[v] = cost[node] + w;
pq.push({-w, v});
}
}
}
minCost = min(minCost, cost[0]);
return visited[0] ? minCost : -1;
}
