#PY0028. 士兵调度

士兵调度

Description

A国有N个城市,其中国王住在编号为S的城市中。

整个国家通过N-1条无向边连接起来,嗯,就是一棵树的结构了

国王有若干个儿子住在叶子城市中。

为了保护这些王子,国王在城市的连通线上安排了一些士兵。

现在为了体现他的均衡,国王决定再多派一些士兵到某些边上,使得从S城出发到任一个叶子点 其路径上的士兵数量是一样的。

请问国王最少要派多少个士兵,注意:你需要最优安排某些边上的新增士兵数量,以使得在满足条件的情况下新增士兵数量最少。

Format

Input

第一行给出N

第二行给出S

接下来N-1行,每行三个数字a,b,c代表a城到b城的边上有c名士兵

N ≤ 500000

c≤ 1000000

Output

如题

Samples

3
1
1 2 1
1 3 3
2