##### National Olympiad in Informatics, China, 2002

The mythical Kuzuryū (nine-headed dragon) is an incredibly greedy creature. Although it is called the "nine-headed dragon", this only refers to how it has nine heads when it is born. As it grows up, it will eventually sprout many new heads, totalling a number far greater than nine. Of course, there will always be old heads that fall off as a result of aging.

One day, a Kuzuryū with heads witnesses a fruit tree containing fruits. Ecstatic, it simply wants to eat them all in one bite. However it must take care of each head, so it needs to split the fruits into groups, one for each head to eat, with at least one fruit per group.

Among these heads there exists a largest one, known as the "boss",
and it serves as the leader of all the heads. *This head would like to
eat exactly fruits, and these fruits should naturally contain
the one and only largest fruit.* The fruits are joined using
branches; due to the fruit tree being a whole, it is possible to start
at a fruit and "arrive at" any other fruit by traveling along its
branches.

Regarding each tree branch segment: If the two fruits it connects require different heads to eat, then the two heads together will break the branch and split up the fruits. If the two fruits are eaten by the same head, then this head will not be bothered to break the branch, and will consequently just eat the entire branch along with the fruits. Of course, eating branches is not too comfortable, so every branch possesses a "pain value" for being eaten. Furthermore, the pain that the Kuzuryū experiences is the sum of the pain values for all of the branches that it has eaten.

The Kuzuryū would like to keep the pain that it experiences to a minimum. Can you help calculate this value?

The smaller head eats fruits, depicted by the white dots.

The Kuzuryū experiences a pain of , since it eats the branch with a pain value of , denoted by a thin line. The first diagram indicates the status of the fruit tree, while the second diagram illustrates the optimal eating strategy.

#### Input Specification

The first line of input contains three integers ,
, and . indicates the number
of fruits, labeled . *The largest fruit is always fruit
number .* Line to line describe the status of the fruit tree,
with each line containing three integers , ,
and , indicating that the
branch connecting fruit and fruit has a pain value of .

#### Output Specification

The output should consist of one line containing a single integer – the
minimum possible pain that the Kuzuryū needs to experience under the
conditions discussed above. If the conditions cannot be satisfied,
output `-1`

.

#### Sample Input

```
8 2 4
1 2 20
1 3 4
1 4 13
2 5 10
2 6 12
3 7 15
3 8 5
```

#### Sample Output

`4`

Problem translated to English by .

## Comments