#P17751. 商贸往来
商贸往来
题目描述
K国有座城市,条有距离的双向道路连接了这个城市。作为贸易大国,K国想修建个城市作为商贸中心城市。每个商贸中心城市都对外国城市有一定的商贸往来,所以本国的城市之间的连接变得尤为重要。
现在K国国王认为,所有商贸城市两两距离之和与其余城市两两距离之和 的和为K国的商贸值。他想让这个商贸值变得最大。于是他将计算最大商贸值的任务交给了你。
输入格式
从标准输入读入。 输入第一行包括两个整数,代表K国的城市数以及商贸城市数。
接下来行,每行个数,代表城市到城市有一条双向道路,长度为。
输出格式
输出到标准输出。 你需要输出最大商贸值。
样例输入
6 4
1 2 4
2 3 5
2 4 5
3 5 2
5 6 4
样例输出
72
样例说明
选择了四座城市作为商贸城市。
注意常数级别的优化
数据范围
对于20%的数据,
对于40%的数据,,第条道路连接了第个城市和第个城市
对于另30%的数据,
对于100%的数据,