#include<bits/stdc++.h>
using namespace std;
const double INF = 1e8;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
k = min(k, 100);
vector<vector<pair<int, double>>> adj(n);
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]});
}
vector<double> dist(n, INF), temp(n, INF);
priority_queue<pair<double, int>> pq;
for(auto &p : temp) p = INF;
for(auto i = 0; i < k; i++) {
pq.push({0, i});
temp[i] = 0.;
}
while(!pq.empty()) {
auto [cur, u] = pq.top(); pq.pop();
if(cur != -dist[u]) continue;
for(auto [v, w] : adj[u]) {
if(temp[v] > cur + w) {
temp[v] = cur + w;
pq.push({-temp[v], v});
}
}
}
double ans = INF;
for(auto &p : temp) p = INF;
for(auto i = 0; i < k; i++) {
pq.push({0, i});
temp[i] = 0.;
}
while(!pq.empty()) {
auto [cur, u] = pq.top(); pq.pop();
if(cur != -dist[u]) continue;
for(auto [v, w] : adj[u]) {
if(temp[v] > cur + w) {
temp[v] = cur + w;
pq.push({-temp[v], v});
}
}
}
ans = min(ans, temp[h]);
return ans < INF ? ans : -1.;
}
