#include <bits/stdc++.h>
using namespace std;
struct state
{
int weight, node;
friend bool operator<(state a, state x)
{
return a.weight > x.weight;
}
};
vector<double> dp;
vector<vector<pair<int, int>>> adjlist;
vector<int> type;
vector<bool> visited;
vector<int> zeroes;
int target;
void recur2sub3(int node, double len)
{
visited[node] = 1;
if (type[node] == 0)
{
zeroes.push_back(node);
return;
}
for (auto a : adjlist[node])
if (!visited[a.first])
recur2sub3(a.first, len + a.second);
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
target = H;
type = arr;
dp.clear();
adjlist.clear(), zeroes.clear(), visited.clear();
visited.resize(N, 0), adjlist.resize(N);
for (int i = 0; i < M; i++)
adjlist[x[i]].push_back({ y[i], c[i] }), adjlist[y[i]].push_back({ x[i], c[i] });
dp.resize(N, 1e15);
recur2sub3(H, 0);
priority_queue<state> pqs;
pqs.push({ 0, H });
while (!pqs.empty())
{
state tmp = pqs.top();
pqs.pop();
if (tmp.weight < dp[tmp.node])
{
dp[tmp.node] = tmp.weight;
for (auto a : adjlist[tmp.node])
if (tmp.weight + a.second < dp[a.first])
pqs.push({ tmp.weight + a.second, a.first });
}
}
double mini = dp[0];
for (auto a : zeroes)
mini = min(mini, dp[a]);
return mini;
}
