问题描述

人类在火星上发现了一种新的金属！这些金属分布在一些奇怪的地方，不妨叫它节点好了。一些节点之间有道路相连，所有的节点和道路形成了一棵树。一共有  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
2  3  1
2  4  1000
2  5  1000
1  6  1000

样例输出
3004

样例说明
所有机器人在  1  号节点着陆。
第一个机器人的行走路径为  1-> 6  ，在  6  号节点返回地球，花费能量为1000。
第二个机器人的行走路径为  1-> 2-> 3-> 2-> 4  ，在  4  号节点返回地球，花费能量为1003。
第一个机器人的行走路径为  1-> 2-> 5  ，在  5  号节点返回地球，花费能量为1001。

数据规模与约定
本题有10个测试点。
对于测试点  1~2  ，  n  < =  10  ，  k  < =  5  。
对于测试点  3  ，  n  < =  100000  ，  k  =  1  。
对于测试点  4  ，  n  < =  1000  ，  k  =  2  。
对于测试点  5~6  ，  n  < =  1000  ，  k  < =  10  。
对于测试点  7~10  ，  n  < =  100000  ，  k  < =  10  。
道路的能量  w  均为不超过  1000  的正整数。