#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define pb push_back
#define ll long long
#define ld long double
#define ui uint64_t
#define ar array
#define us unordered_set
#define cont(set, element) ((set).find(element) != (set).end())
/********* DEBUG *********/
template <typename T>
void outvec(const vector<T>& Z, int hi = INT_MAX) {
int count = 0;
for (const T& x : Z) {
if (count >= hi) break;
cout << x << ' ';
count++;
}
cout << "\n";
}
// overloaded function for raw arrays
template <typename T, size_t N>
void outvec(const T (&arr)[N], int hi = INT_MAX) {
int count = 0;
for (size_t i = 0; i < N; ++i) {
if (count >= hi) break;
cout << arr[i] << ' ';
count++;
}
cout << "\n";
}
/********* DEBUG *********/
const ll inf = 1e18;
const int MOD = 1e9+7;
const int MOD2 = 998244353;
const int mxN = 200005;
// Subtask arr ∈ {0,1}
// DSU, find all possible starting places
// Push all starting nodes to Djikstra
int parent[100005];
int _find(int x){
if (parent[x] != x)
parent[x] = _find(parent[x]);
return parent[x];
}
void _uni(int x, int y){
x = _find(x);
y = _find(y);
parent[x] = y;
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> power){
// cst, node
vector<vector<pair<double, int>>> adj(N);
priority_queue<pair<double,int>, vector<pair<double,int>>, greater<pair<double,int>>> minheap;
for (int i = 0; i < M; i++){
adj[x[i]].pb({c[i], y[i]});
adj[y[i]].pb({c[i], x[i]});
}
vector<bool> visited(N);
queue<int> q;
minheap.push({0,0});
q.push(0);
visited[0] = true;
while (q.size()){
int x = q.front(); q.pop();
if (power[x] == 0){
minheap.push({0, x});
}
for (auto &y : adj[x]){
int nd = y.second;
if (nd != H && !visited[nd]){
visited[nd] = true;
q.push(nd);
}
}
}
for (int i = 0; i < N; i++){
visited[i] = false;
}
while (minheap.size()){
auto z = minheap.top(); minheap.pop();
int nd = z.second;
double cst = z.first;
if (nd == H){
return cst;
}
visited[nd] = true;
for (auto &y : adj[nd]){
int newnd = y.second;
double newcst = y.first;
if (!visited[newnd]){
minheap.push({newcst + cst, newnd});
}
}
}
return -1;
}
