#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
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<pll>> G(N);
vector<double> dis(N);
vector<bool> v(N);
for (int i = 0; i < M; i++) {
G[x[i]].push_back({y[i], c[i]});
G[y[i]].push_back({x[i], c[i]});
}
if (N == 2 && !M) return -1;
else if (N == 2)
return c[0];
priority_queue<pair<double, ll>, vector<pair<double, ll>>,
greater<pair<double, ll>>>
q;
arr[0] = 0;
{
vector<bool> v(N);
queue<ll> qt;
qt.push(0);
while (qt.size()) {
ll node = qt.front();
qt.pop();
if (v[node] || node == H) continue;
v[node] = true;
if (!arr[node]) q.push({0, node});
for (pll& nei : G[node]) qt.push(nei.first);
}
}
double ans = LLONG_MAX;
while (q.size()) {
ll node = q.top().second;
double c = q.top().first;
q.pop();
if (node == H) ans = min(ans, c);
if (v[node] || node == H) continue;
v[node] = true;
for (pll& nei : G[node]) q.push({nei.second + c, nei.first});
}
if (ans == LLONG_MAX) return -1;
return ans;
}
