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