#P17751. 商贸往来

商贸往来

题目描述

K国有nn座城市,n−1n-1条有距离的双向道路连接了这nn个城市。作为贸易大国,K国想修建ww个城市作为商贸中心城市。每个商贸中心城市都对外国城市有一定的商贸往来,所以本国的城市之间的连接变得尤为重要。

现在K国国王认为,所有商贸城市两两距离之和与其余城市两两距离之和 的和为K国的商贸值。他想让这个商贸值变得最大。于是他将计算最大商贸值的任务交给了你。

输入格式

从标准输入读入。 输入第一行包括两个整数n,wn,w,代表K国的城市数以及商贸城市数。

接下来n−1n-1行,每行33个数x,y,lenx,y,len,代表城市xx到城市yy有一条双向道路,长度为lenlen。

输出格式

输出到标准输出。 你需要输出最大商贸值。

样例输入

6 4
1 2 4
2 3 5
2 4 5
3 5 2
5 6 4

样例输出

72 

样例说明

选择了1,4,5,61,4,5,6四座城市作为商贸城市。

注意常数级别的优化

数据范围

对于20%的数据,n≤10n \le 10

对于40%的数据,n≤500n \le 500,第ii条道路连接了第ii个城市和第i+1i+1个城市

对于另30%的数据,n≤500n \le 500

对于100%的数据,1≤n≤5000,1≤w≤n,1≤len≤1061 \le n \le 5000,1 \le w \le n,1 \le len \le 10^6