Description

To protect Gensokyo, 冴月麟 created a reflection of Gensokyo and sealed away the real Gensokyo. No one can enter the real Gensokyo anymore, but she left a clue for 魏潇承 who came to save her.

She set up a rooted tree. Each edge has a cost to cut it.

魏潇承 needs to compute the minimum cost to cut this tree. This is the little secret agreed upon by 冴月麟 and 魏潇承.

Please help 魏潇承.

Note: To “cut open” a rooted tree means to delete some edges so that no leaf node is connected to the root.

Input Format

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

Each of the next $n-1$ lines contains three integers $a, b, c$, indicating there is an edge between $a$ and $b$ with cost $c$.

Output Format

Output one line containing a single integer, the minimum cost.

4 1
1 2 1 
1 3 1
1 4 1

3

4 1
1 2 3
2 3 1
3 4 2

1

Hint

Constraints and Agreements

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

Translated by ChatGPT 5