#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll LL_INF = (ll)1e18+1;
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, int>>> adj(N);
for(int i = 0; i < M; ++i) {
adj[x[i]].emplace_back(y[i], c[i]);
adj[y[i]].emplace_back(x[i], c[i]);
}
vector<ll> dist(N, LLONG_MAX);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> dijkstra;
dijkstra.emplace(0, 0);
queue<int> bfs; bfs.push(0);
vector<bool> visited_0(N);
while(!bfs.empty()) {
int u = bfs.front(); bfs.pop();
if(visited_0[u]) continue;
visited_0[u] = true;
if(arr[u] == 0) dijkstra.emplace(0, u);
if(u == H) continue; // we can't move from H
for(auto [v, c]: adj[u]) bfs.push(v);
}
while(!dijkstra.empty()) {
auto [d, u] = dijkstra.top();
dijkstra.pop();
if(d >= dist[u]) continue;
dist[u] = d;
for(auto [v, cv]: adj[u]) {
dijkstra.emplace(d + cv, v);
}
}
if(dist[H] == LLONG_MAX) return -1;
return dist[H];
}
