#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
vector<bool> vis(1e5), vab(1e5);
vector<double> dist(1e5);
vector<vector<pair<int, int>>> adj(1e5);
void dfs(int u){
vab[u] = 1;
for (auto x: adj[u]){
if (!vab[x.first]) dfs(x.first);
}
}
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
for (int i = 0; i < n; i++){
vis[i] = 0;
vab[i] = 0;
dist[i] = 1e18;
adj[i].clear();
}
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
for (int i = 0; i < m; i++){
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
dfs(0);
if (vab[h] == 0) return -1;
for (int i = 0; i < n; i++){
if (i == 0 || arr[i] == 0) pq.push({0, i});
}
while (pq.size()){
long long d = pq.top().first;
int in = pq.top().second;
pq.pop();
if (vis[in]) continue;
vis[in] = 1;
dist[in] = d;
for (auto z: adj[in]){
pq.push({d + z.second, z.first});
}
}
return dist[h];
}
