#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
#define f(i,a,b) for(int i = a; i < b; i++)
typedef pair <double, int> ii;
const int N = 1e5 + 5;
const double inf = 2e9;
int n;
double d[N];
bool vis[N];
vector <pair<int, double>> adj[N], adj_H;
vector <int> ARR;
void check(int u){
vis[u] = 1;
for(auto p: adj[u]){
int v = p.first;
if(!vis[v]) check(v);
}
}
void clear(){
adj_H.clear(); ARR.clear();
f(i,0,n) adj[i].clear(), vis[i] = 0;
}
void dij(){
priority_queue <ii, vector <ii>, greater <ii>> q;
f(i,0,n) {
d[i] = inf;
if((ARR[i] == 0 or i == 0) and vis[i]){
d[i] = 0;
q.push({0, i});
}
}
while(!q.empty()){
auto pa = q.top(); q.pop();
double d_u = pa.first; int u = pa.second;
if(d[u] != d_u) continue;
for(auto p: adj[u]){
int v = p.first; double w = p.second;
if(d[v] > d[u] + w){
d[v] = d[u] + w;
q.push({d[v], v});
}
}
}
}
double solve(int Ni, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
n = Ni;
ARR = arr;
f(i,0,M){
if(x[i] == H or y[i] == H){
adj_H.push_back({x[i] + y[i] - H, c[i]});
}
else {
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
}
check(0);
dij();
double ans = inf;
for(auto p: adj_H) {
int v = p.first; double w = p.second;
if(vis[v]) ans = min(ans, d[v] + w);
}
clear();
return (ans == inf) ? -1 : ans;
}
