Another Cola Machine 公司，简称 **ACM**，是瓦特星的巨头企业

该公司的数据网络呈现一个 结构

Y 结构在图论上，可视作一棵特殊的树：

1. 一个核心节点，代表 ACM 总部，度数为

2. 若干传输节点，度数为

3. 三个数据库节点，度数为

4. 连接两个节点 的无向边，边权为

---

你是 high 客联盟的秘密首脑 Nobody，代号 N

为了向 ACM 公司展现你们联盟的实力，你决定黑入该公司的三个数据库，删掉所有的 Cola Logo

你已经提前了解到了整个数据网络的布局

---

黑入第 个数据库的风险值 定义为： **核心节点** 到 **该数据库节点** 路径上的 **所有边权之和**

总风险值 定义为三个风险值的最大值，即

你可以选择最多 个脉冲设备，每个脉冲设备可以选择一条边，使其权值

为了确保行动成功，你希望找出一个最优方案，能够令 最小

第一行包含两个正整数  ，分别代表  结构的节点数量和脉冲设别数量

接下来的  行，每行包含三个正整数  ，代表一条连接节点  的边，其边权为 

输出一个 ，代表最小的总风险值

4 1
1 4 7
4 3 9
2 4 6

7

7 3
7 2 200
7 1 200
7 3 1
3 4 100
4 5 99
5 6 99

199