题目描述

人类在火星上发现了一种新的金属！这些金属分布在一些奇怪的地方，不妨叫它节点好了。一些节点之间有道路相连，所有的节点和道路形成了一棵树。一共有 $n$ 个节点，这些节点被编号为 $1$ 到 $n$。

人类将 $k$ 个机器人送上了火星，目的是采集这些金属。这些机器人都被送到了一个指定的着陆点，$S$ 号节点。每个机器人在着陆之后，必须沿着道路行走。当机器人到达一个节点时，它会采集这个节点蕴藏的所有金属矿。当机器人完成自己的任务之后，可以从任意一个节点返回地球。当然，回到地球的机器人就无法再到火星去了。

我们已经提前测量出了每条道路的信息，包括它的两个端点 $x$ 和 $y$，以及通过这条道路需要花费的能量 $w$。我们想花费尽量少的能量采集所有节点的金属，这个任务就交给你了。

输入格式

第一行包含三个整数 $n, S, k$，分别代表节点个数、着陆点编号和机器人个数。

接下来一共 $n-1$ 行，每行描述一条道路。一行含有三个整数 $x, y, w$，代表在 $x$ 号节点和 $y$ 号节点之间有一条道路，通过需要花费 $w$ 个单位的能量。所有道路都可以双向通行。

输出格式

输出一个整数，代表采集所有节点的金属所需要的最少能量。

样例

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

3004

样例解释

所有机器人在 $1$ 号节点着陆。

• 第一个机器人的行走路径为 $1 \to 6$，在 $6$ 号节点返回地球，花费能量为 $1000$。
• 第二个机器人的行走路径为 $1 \to 2 \to 3 \to 2 \to 4$，在 $4$ 号节点返回地球，花费能量为 $1003$。
• 第三个机器人的行走路径为 $1 \to 2 \to 5$，在 $5$ 号节点返回地球，花费能量为 $1001$。

数据范围

• $2 \le n \le 10^5$
• $1 \le k \le 100$
• $1 \le w \le 1000$

来源

蓝桥杯练习系统