#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using std::vector;
using std::pair;
using std::priority_queue;
using std::min;
using std::max;
vector<vector<pair<int, int>>> adj;
vector<bool> vis;
pair<int, int> dfs(int u, int dist, int depth, int t) {
vis[u] = true;
if (u == t) return {dist, depth};
pair<int, int> res = {1e9, 1e9};
for (auto &p: adj[u]) {
int v = p.first;
int w = p.second;
if (vis[v]) continue;
res = min(res, dfs(v, dist + w, depth + 1, t));
}
return {dist, depth};
}
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
adj.assign(n, {});
vis.assign(n, false);
for (int i = 0; i<m; ++i) {
int u = x[i], v = y[i], w = c[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
pair<int, int> res = dfs(0, 0, 0, h);
return (res.second <= k ? res.first : -1);
}
// int main() {
// int res = solve()
// }
