H. 分身游走

A 国有编号为 到 的 个城市，由 条双向道路连接，而且无论从哪个城市出发都能通过沿着道路到达任意城市。

小 B 学会了分身术！具体地，他可以在城市 召唤至多 个分身。为了品尝到每个城市的美食来解馋，她会停留在城市 操控自己的分身们四处游走，目标是使得每个城市被至少一个分身经过。但是操控分身移动是很累的，你也不希望小 B 太累，所以希望他的所有分身走过的总路程长度最小。

可惜的是，小 B 还没有决定好起点城市 ，于是请你求出每个城市作为起点，操纵至多 个分身从起点出发，经过所有城市时的最小总路程。

第一行两个整数分别表示城市的数量和分身的数量。

第二行到第行共行，每行三个整数表示存在一条连接城市,长度为的双向道路。

第一行到第 行共 行，第 行一个整数表示以城市 为起点时，所有分身走过的最小总路程。

输入

5 3
1 2 7
2 3 5
3 4 14
3 5 8

输出

42
39
34
42
42

样例解释

对于以城市 1 为起点的情况，一种最优的策略为，一号分身，二三号分身停留在起点不游走，总路程为 。

对于所有数据 。