#include <bits/stdc++.h>
#include "cyberland.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 1e5+10;
const int MAXK = 105;
const double INF = 1e16+10;
const ll MOD = 1e9 + 7;
const ll LOG = 20;
typedef pair<int,int> pii;
typedef pair<int,double> piii;
typedef pair<double, int> ipii;
int n, m, k, h;
double dp[MAXK][MAXN];
vector <pii> adj[MAXN];
priority_queue <ipii, vector<ipii>, greater<ipii>> pq;
//priority_queue <ipii> pq;
bool vis[MAXN];
vector <piii> en;
void reset(){
en.clear();
for(int i=0; i<n; i++){
adj[i].clear();
vis[i] = 0;
}
}
void dfs(int nw){
if(vis[nw]) return;
vis[nw] = 1;
for(auto nx : adj[nw]){
dfs(nx.fi);
}
}
void dji(int idx){
for(int i=0; i<n; i++) pq.push(ipii(dp[idx][i], i));
while(!pq.empty()){
double dis = pq.top().fi; int nw = pq.top().se; pq.pop();
if(dis > dp[idx][nw]) continue;
for(auto ed : adj[nw]){
int nx = ed.fi; double wei = ed.se;
if(dp[idx][nx] > dp[idx][nw] + wei){
dp[idx][nx] = dp[idx][nw] + wei;
pq.push(ipii(dp[idx][nx], nx));
}
}
}
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
n = N; m = M; k = K; h = H; k = min(k, 100);
reset();
for(int i=0; i<=m-1; i++){
if(x[i] == h) en.pb(pii(y[i], c[i]));
else if(y[i] == h) en.pb(pii(x[i], c[i]));
else {
adj[x[i]].pb(pii(y[i], c[i])); adj[y[i]].pb(pii(x[i], c[i]));
}
}
dfs(0);
// step 1
for(int i=0; i<n; i++){ //idx = sta-en
for(int j=0; j<=k; j++) dp[j][i] = INF;
}
for(int i=0; i<n; i++) {
if(vis[i] && arr[i] == 0) dp[0][i] = 0;
}
dp[0][0] = 0;
/*for(auto in : vec)cout << in.fi << ' ' << in.se << "in\n";
cout << sta << ' ' << en << "sta\n";
return 0;*/
//dji(0);
for(int j=0; j<=k; j++){
// step 3
if(j!=0){
for(int i=0; i<n; i++){
if(!vis[i] || arr[i]!=2) continue;
for(auto ed : adj[i]){
int nx = ed.fi; int wei = ed.se;
dp[j][i] = min(dp[j][i], (dp[j-1][nx]+wei)/2);
}
}
}
// step 4
dji(j);
// for(int i=1; i<=h-1; i++){
// dp[j][i] = min(dp[j][i], dp[j][i-1]+c[i-1]);
// }
// for(int i=h-2; i>=0; i--){
// dp[j][i] = min(dp[j][i], dp[j][i+1]+c[i]);
// }
}
/*for(int i=sta; i<=en; i++){
for(int j=0; j<=k; j++) cout << dp[i][j] << ' ';
cout << '\n';
}*/
// step 5
double ans = INF;
for(int i=0; i<=k; i++){
for(auto in : en) ans = min(ans, dp[i][in.fi]+in.se);
}
if(ans==INF) return -1;
return ans;
}
