时态同步
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
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