P16334 [DSDOI Round 1] 邓少大肉粽

邓少又想吃大肉粽了，但这次他决定自己去买。

学校饭堂可以视作一颗有 $n$ 个点的树，所有边均为双向边，每个点上都有一个大肉粽。 邓少从 $1$ 号点出发，想要到达所有的点，获得所有的大肉粽。**他在经过所有的点以后，不需要回到 $1$ 号点。** 若邓少现在在点 $u$，那么他可以选择一条边 $(u, v, w)$，然后他会耗费 $w$ 的时间，从点 $u$ 移动到点 $v$。 但在去饭堂之前，他可以**任意选定**其中的 $m$ 条边，用吃霸王餐剩下的钱，委托同学把这 $m$ 条边的地面拖湿（这样他就可以直接滑过去了）。于是这 $m$ 条边的时间花费将**永久**变为 $0$。 邓少想知道，他获得所有大肉粽至少需要多长时间。

第一行包含两个正整数 $n,m$，分别表示节点数量和可以修改时间花费为 $0$ 的边数。 接下来有 $n - 1$ 行，其中每一行包含三个整数 $u_i,v_i,w_i$，表示有一条连接 $u_i,v_i$ 的双向边，时间花费为 $w_i$。

输出一行，包含一个正整数，表示邓少经过所有点所需的最小时间。

**本题采用捆绑测试。** ### 【数据范围】 对于所有测试数据，保证： - $1\le n\le 10^6$； - $0\le m\le n-1$； - $1\le u_i,v_i\le n$，$1\le w_i\le 2\times 10^5$； - 保证叶子节点数不超过 $2\times 10^5$。 | Subtask 编号 | 测试点编号 | $n\le$ | $m$ | 分值 | | :-: | :-: | :-: | :-: | :-: | | $0$ | $1\sim2$ | $10$ | $\le n-1$ | $10$ | | $1$ | $3\sim5$ | $10^3$ | ^ | $20$ | | $2$ | $6\sim7$ | $10^6$ | $=0$ | $20$ | | $3$ | $8\sim15$ | ^ | $\le n-1$ | $50$ |