#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
// subtask 1
// ll ac(ll k, ll f)
// {
// // cout << k << " " << f;
// if (f == 0)
// {
// return 0;
// }
// else if (f == 2)
// {
// return k / 2;
// }
// else
// {
// return k;
// }
// };
// ll _(ll k)
// {
// return k == 2 ? 1 : 2;
// }
// ll solve(ll N, ll M, ll K, ll H, std::vector<ll> x, std::vector<ll> y, std::vector<ll> c, std::vector<ll> arr)
// {
// ll MAX = (5.0e10 + 0.1);
// vector<vector<ll>> C(3, vector<ll>(3, MAX));
// vector<vector<bool>> V(3, vector<bool>(3, false));
// for (ll i = 0; i < M; i++)
// {
// C[x[i]][y[i]] = min(C[x[i]][y[i]], (ll)c[i]);
// C[y[i]][x[i]] = min(C[y[i]][x[i]], (ll)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]);
// }
class DSU
{
public:
vector<int> parent;
DSU(int k)
{
parent.resize(k);
for (int i = 0; i < k; i++)
{
parent[i] = i;
}
}
int find(int k)
{
assert(k < parent.size());
if (parent[k] == k)
{
return k;
}
return parent[k] = find(parent[k]);
}
void takeover(int i, int j)
{
int pi = find(i);
int pj = find(j);
// cout << pi << " " << pj << "\n";
parent[pj] = pi;
}
};
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<ll, ll>>> adj(N);
vector<ll> cost(N, 5e17);
vector<bool> visited(N, false);
DSU check(N);
ll minCost = 5e17;
for (ll i = 0; i < M; i++)
{
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
check.takeover(x[i], y[i]);
}
priority_queue<pair<ll, ll>> pq;
cost[H] = 0;
pq.push({0, H});
// cout << pq.top().first << " \n";
while (!pq.empty())
{
ll cst = -pq.top().first;
ll node = pq.top().second;
pq.pop();
visited[node] = true;
if (arr[node] == 0)
{
minCost = min(minCost, cost[node]);
}
for (ll i = 0; i < adj[node].size(); i++)
{
ll v = adj[node][i].first;
ll 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 check.find(0) == check.find(H) ? minCost : -1;
}
