Xiao Q is learning to solder circuit boards in an electronics internship. A circuit board consists of several components, which we can call nodes, labeled with numbers $1, 2, 3, \dots$. The nodes of the circuit board are connected by several non-intersecting wires, and for any two nodes on the board, there exists exactly one path (a path is a sequence of wires connecting two components).

There is a special component on the circuit board called an "exciter." When the exciter is activated, it generates an excitation current that travels through the wires to every node it is connected to. When an intermediate node receives the excitation current, it obtains the information and transmits the current to all nodes connected to it that have not yet received the excitation current. Eventually, the excitation current will reach some "terminal nodes"—nodes that do not forward the current after receiving it.

The propagation of the excitation current through a wire takes time. For each edge $e$, the time required for the excitation current to pass through it is $t_e$, and the forwarding of the current by a node after receiving it can be considered instantaneous.

Now, the circuit board requires every "terminal node" to receive the excitation current at the same time—that is, to maintain temporal synchronization. Since the current construction does not meet the requirements for temporal synchronization, it is necessary to change the construction of the connections. Xiao Q currently has a tool; using this tool once can increase the time it takes for the excitation current to pass through a certain connecting wire by one unit. What is the minimum number of times Xiao Q needs to use the tool to make all "terminal nodes" temporally synchronized?

Input

The first line contains a positive integer $N$, representing the number of nodes on the circuit board. The second line contains an integer $S$, the label of the exciter on the circuit board. The next $N-1$ lines each contain three integers $a, b, t$, representing that the wire connects node $a$ and node $b$, and the excitation current takes $t$ units of time to pass through this wire.

Output

The output contains a single integer $V$, the minimum number of times Xiao Q needs to use the tool.

Examples

Input 1

3
1
1 2 1
1 3 3

Output 1

2

Constraints

For 40% of the data, $N \le 1000$. For 100% of the data, $N \le 500000$. For all data, $t_e \le 1000000$.