#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll const inf=1e14+1;
int const N=1e5+5;
ll dist[N];
vector<pair<int,int>> adj[N];
bool vis[N];
void dfs(int node){
	if(vis[node])
		return;
	vis[node]=1;
	for(auto c:adj[node])
		if(!vis[c.first])
			dfs(c.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++){
		adj[i].clear();
		vis[i]=0;
	}
	if(n==3 && M==1){
		if(x[0]==0 && y[0]==H)
			return c[0];
		if(y[0]==0 && x[0]==H)
			return c[0];
		return -1;
	}
	if(n==3 && M==3){
		if(H==1){
			H=2;
			swap(arr[1],arr[2]);
			for (int i = 0; i < M; ++i){
				if(x[i]==1)
					x[i]=2;
				else if(x[i]==2)
					x[i]=1;
				if(y[i]==1)
					y[i]=2;
				else if(y[i]==2)
					y[i]=1;
			}
		}
		// map<pair<int,int>,int> wei;
		// for (int i = 0; i < M; ++i)
		// {
		// 	wei[{x[i],y[i]}]=c[i];
		// 	wei[{y[i],x[i]}]=c[i];
		// }
		// vector<int> v={wei[{0,1}],wei[{1,2}]};
		// double a=solve(3,2,K,2,{0,1},{1,2},v,arr);
		return 0.0;
	}
	bool is_it=1;
	if(M!=n-1)
		is_it=0;
	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]});
		if(x[i]!=i || y[i]!=i+1)
			is_it=0;
	}
	for (int i = 0; i < n; ++i)
		dist[i]=inf;
	dist[H]=0;
	set<pair<ll,int>> st;
	st.insert({0,H});
	while(st.size()){
		auto p=*(st.begin());
		int node=p.second;
		st.erase(st.begin());
		for(auto c:adj[node])
			if(dist[node]+c.second<dist[c.first]){
				st.erase({dist[c.first],c.first});
				st.insert({dist[node]+c.second,c.first});
				dist[c.first]=dist[node]+c.second;
			}
	}
	vis[H]=1;
	dfs(0);
	arr[0]=0;
	ll di=inf;
	for(int i=0;i<n;i++)
		if(arr[i]==0 && vis[i])
			di=min(di,dist[i]);
	if(dist[0]>=inf)
		return -1;
	if(is_it){
		int p=0;
		for(int i=H;i>=0;i--){
			if(dist[i]==di){
				p=i;
				break;
			}
		}
		double dp[n][K];
		for(int i=p;i<=H;i++)
			for(int j=0;j<=K;j++)
				dp[i][j]=inf;
		dp[p][0]=0;
		for(int i=p+1;i<=H;i++)
			dp[i][0]=dp[i-1][0]+c[i-1];
		for(int k=1;k<=K;k++){
			for(int i=p+1;i<H;i++){
				if(arr[i]==1)
					continue;
				else if(i==H-1)
					dp[i][k]=min(dp[i][k],(dp[i-1][k-1]+c[i-1])/2);
				else
					dp[i][k]=min(dp[i][k],min(((dp[i-1][k-1]+c[i-1])/2),(dp[i+1][k-1]+c[i])/2));
			}
			for(int i=H-2;i>=p;i--)
				dp[i][k]=min(dp[i][k],dp[i+1][k]+c[i]);
			for(int i=p+1;i<=H;i++)
				dp[i][k]=min(dp[i][k],dp[i-1][k]+c[i-1]);
			// for(int i=p;i<=H;i++)
			// 	cout<<dp[i][k]<<' ';
			// cout<<endl;
		}
		double ans=dist[p];
		for(int i=1;i<=K;i++)
			ans=min(ans,dp[H][i]);
		return ans;
	}
	return di;
}