题目描述

小 Q 在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，称之为节点，编号为 $1,2,\dots,N$。节点之间由导线相连，任意两个节点之间有且仅有一条通路（也就是说，电路板是一棵树）。

电路板上有一个特殊的元件叫“激发器”。激发器工作后产生激励电流，通过导线传向它连接的每一个节点。中间节点收到激励电流后，再把它传给与它相连、还没收到电流的节点。最终电流到达一些“终止节点”——收到电流后不再转发的节点。

电流通过导线 $e$ 需要的时间是 $t_e$，节点转发是瞬间完成的。现在要求所有终止节点同时收到激励电流，即保持时态同步。小 Q 有一个道具，用一次可以让电流通过某一条导线的时间增加 $1$ 个单位。问最少用多少次道具，才能让所有终止节点时态同步？

输入格式

第一行一个正整数 $N$，表示节点个数。

第二行一个整数 $S$，表示激发器的编号。

接下来 $N-1$ 行，每行三个整数 $a,b,t$，表示一条连接节点 $a$ 和 $b$ 的导线，电流通过它需要 $t$ 个单位时间。

输出格式

一行一个整数，表示最少使用道具的次数。

样例

3
1
1 2 1
1 3 3

2

数据范围与提示

样例解释：把 $1$–$2$ 这条导线用 $2$ 次道具，两个终止节点都在时刻 $3$ 收到电流。

对于全部数据，$1\le t_e\le 10^6$。保证以激发器为根时，树的深度不超过 $3\times 10^4$（可以放心写递归 DFS）。

来源：洛谷 P1131 [ZJOI2007] 时态同步。