P3931 SAC E#1 - A Hard Problem Tree

冴月麟 and 魏潇承 are good friends.

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.

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 one line containing a single integer, the minimum cost.

### 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