Background

Sedum麟 and Wei Xiaocheng are good friends.

Problem Description

Sedum麟 created a mirror image of Gensokyo to protect it, sealing away the real Gensokyo. No one can enter the real Gensokyo anymore, but she left a clue for Wei Xiaocheng, who came to rescue her.

She set up a rooted tree. Each edge in the tree has a cost associated with cutting it.

Wei Xiaocheng needs to calculate the minimum cost to cut the tree, which is the secret agreement between Sedum麟 and Wei Xiaocheng.

Help Wei Xiaocheng with this task.

Note: Cutting a rooted tree means deleting several edges such that no leaf node is connected to the root node.

Input and Output Formats

Input Format

The first line of input contains two integers $n$ and $\mathrm{root}$, representing the number of nodes in the tree and the root node, respectively.

The next $n-1$ lines each contain three integers $a$, $b$, and $c$, indicating that there is an edge between $a$ and $b$ with a cost of $c$.

Output Format

The output should contain one line with a single integer, representing the minimum cost required.

Sample Input and Output

Sample Input #1

4 1
1 2 1 
1 3 1
1 4 1

Sample Output #1

3

Sample Input #2

4 1
1 2 3
2 3 1
3 4 2

Sample Output #2

1

Notes

Data Range and Constraints

• For $20\%$ of the data, $n \le 10$;
• For $50\%$ of the data, $n \le 1000$;
• For $100\%$ of the data, $2 \le n \le 100000$, and the edge weights are non-negative integers not exceeding $10^6$.

见题面 Input 部分

见题面 Output 部分