SAC E#1 - 一道难题 Tree

题目背景

冴月麟和魏潇承是好朋友。

题目描述

冴月麟为了守护幻想乡,而制造了幻想乡的倒影,将真实的幻想乡封印了。任何人都无法进入真实的幻想乡了,但是她给前来救她的魏潇承留了一个线索。 她设置了一棵树(有根)。树的每一条边上具有割掉该边的代价。 魏潇承需要计算出割开这棵树的最小代价,这就是冴月麟和魏潇承约定的小秘密。 帮帮魏潇承吧。 注:所谓割开一棵有根树,就是删除若干条边,使得任何任何叶子节点和根节点不连通。

输入输出格式

输入格式


输入第一行两个整数n,S表示树的节点个数和根。 接下来n-1行每行三个整数a、b、c,表示a、b之间有一条代价为c的边。

输出格式


输出包含一行,一个整数,表示所求最小代价。

输入输出样例

输入样例 #1

4 1
1 2 1 
1 3 1
1 4 1

输出样例 #1

3

输入样例 #2

4 1
1 2 3
2 3 1
3 4 2

输出样例 #2

1

说明

对于20%的数据,n <= 10 对于50%的数据,n <= 1000 对于100%的数据,n <= 100000