#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;
	}
	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(n<=3 && M<=1)
		return c[0];
	if(n==3 && M<=3 && is_it==0 && (arr[2]==2 || arr[1]==2)){
		map<pair<int,int>,double> mp;
		for(int i=0;i<3;i++)
			for(int j=0;j<3;j++)
				mp[{i,j}]=inf;
		for(int i=0;i<M;i++){
			mp[{x[i],y[i]}]=c[i];
			mp[{y[i],x[i]}]=c[i];
		}
		if(H==1){
			if(K==0)
				arr[2]=1;
			if(arr[2]==2){
				double ans=mp[{0,2}];
				ans/=2;
				return min(double(mp[{0,1}]),ans+mp[{2,1}]);
			}
			else if(arr[2]==0)
				return min(mp[{0,1}],mp[{2,1}]);
			else
				return min(mp[{0,1}],mp[{0,2}]+mp[{2,1}]);
		}
		else{
			if(K==0)
				arr[1]=1;
			if(arr[1]==2){
				double ans=mp[{0,1}];
				ans/=2;
				return min(double(mp[{0,2}]),ans+mp[{1,2}]);
			}
			else if(arr[1]==0)
				return min(mp[{0,2}],mp[{1,2}]);
			else
				return min(mp[{0,2}],mp[{0,1}]+mp[{1,2}]);
		}
	}
	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;
}