Migrated from Lutece 2796 惊魂工创1

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

大冤种 MichaelZona 在某院著名挑战性课程《工程实践创新项目1》上学习如何焊接PCB板。

一块PCB板上有 $N$ 个元件，我们将其用数字 $1,2,3…N$ 进行标号。PCB板的各个元件由若干不相交的导线相连接，任意两个元件之间有且仅有一条通路连接。其中有一个元件叫触发器，可以通过导线向每一个它所连接的元件发送激励电流。一个元件接收到激励电流后，会将其传向与它连接并且尚未接收到激励电流的元件。最终，激励电流将到达一些“终止节点”——接收激励电流之后不再转发的元件。对于一根导线 $E$，激励电流通过它需要的时间为 $t_E$ ，元件接收和转发激励电流不需要花费时间。对于任何一个板子，保持时态同步是非常重要的，如果你不知道什么是时态同步，你可以理解为每一个“终止节点”需要同时得到激励电流。但是由于 MichaeZona 的水平有限，他并不能一遍就做出符合时态同步的板子，所以他决定慢慢来调这个bug。

现在 MichaelZona 有一个道具，每使用一次该道具，可以使得激励电流通过某条连接导线的时间增加一个单位。请问 MichaelZona 最少使用多少次道具才可使得所有的“终止节点”时态同步？

Input

第一行包含一个正整数 $N$，表示PCB板中元件的个数。

第二行包含一个整数 $S$，为该电路板的激发器的编号。

接下来 $N-1$ 行，每行三个整数 $a,b,t$。表示该条导线连接元件 $a$ 与元件 $b$，且激励电流通过这条导线需要 $t$ 个单位时间。

Output

仅包含一个整数 $V$，为 MichaelZona 最少使用的道具次数。

Samples

3
1
1 2 1
1 3 3

2

Constraints

$N \leq 500000$

$t_E \leq 1000000$

Resources

2022 UESTC ICPC Training for Dynamic Programming