Bonsai

Time limit1sMemory limit128 MB

Summary

Root a weighted tree and cut edges of minimum total weight so that no original leaf stays connected to the root.

Level: Medium6 of 10
Topics: Tree, DFS, Dynamic programming, Greedy
Solved: No attempts yet

Problem

Help chop every leaf off a bonsai tree.

You are given an undirected tree (a connected graph with no cycles) on $n$ vertices. Each edge (a branch) has a nonnegative integer weight (its thickness). One vertex $r$ is the root, and because the graph is a tree, every other vertex has a unique path to the root.

A leaf is a non-root vertex that has no children when the tree is rooted at $r$ — equivalently, a non-root vertex that is not the parent of any other vertex.

Determine the minimum total weight of edges that must be removed so that afterwards no leaf of the original tree is still connected to the root by any path.

Input

The input contains several test cases.

Each test case starts with a line holding two integers $n$ and $r$ ( $1 \le n \le 1000$ , $1 \le r \le n$ ): the number of vertices and the index of the root.

The next $n-1$ lines each hold three integers $u_i$ $v_i$ $w_i$ ( $1 \le u_i, v_i \le n$ , $0 \le w_i \le 1000$ ), meaning there is an undirected edge of weight $w_i$ between vertices $u_i$ and $v_i$ . No edge is listed twice, and the given edges always form a tree.

The input ends with a line containing 0 0, which is not a test case.

Output

For each test case, print a single line with one integer: the minimum total weight of edges that must be removed so that no original leaf is connected to the root.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
2 1
1 2 5
0 0
```
Expected output
```
5
```
Example 3
Input
```
4 1
1 2 5
1 3 3
1 4 8
0 0
```
Expected output
```
16
```