Jungle Roads

Interview

Time limit1sMemory limit128 MB

Summary

Given a connected weighted graph of villages and roads, find the minimum total maintenance cost of a set of roads that keeps every village connected.

Level: Medium4 of 10
Topics: Minimum spanning tree, Graph, Union-find, Greedy
Solved: No attempts yet

Problem

The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maintain. The Council of Elders must choose to stop maintaining some roads.

Of course there must still be some way to travel between all the villages on the maintained roads, even if the route is not as short as before. The Chief Elder would like to tell the Council of Elders the smallest amount they could spend, in aacms per month, to maintain a set of roads that connects all the villages.

The villages are labeled A through I in the maps. The map shows all the roads in use now together with the cost in aacms per month to maintain each one; the cheapest network that keeps every village connected costs 216 aacms per month. Your task is to write a program that solves such problems.

Input

The input consists of one to 100 data sets, followed by a final line containing only 0.

Each data set starts with a line containing only a number $n$ , the number of villages ( $1 < n < 27$ ). The villages are labeled with the first $n$ capital letters of the alphabet.

The data set continues with $n-1$ lines that start with village labels in alphabetical order (there is no line for the last village). Each line starts with the village label, followed by a number $k$ of roads from this village to villages with labels later in the alphabet. If $k$ is greater than 0, the line continues with the data for each of the $k$ roads: the village label of the other end of the road followed by the monthly maintenance cost, in aacms, of that road. Maintenance costs are positive integers less than 100. All data fields on a line are separated by single blanks.

The road network always allows travel between all the villages. The network never has more than 75 roads. No village has more than 15 roads going to other villages (before or after it in the alphabet).

Output

For each data set, output one integer on its own line: the minimum cost in aacms per month to maintain a road system that connects all the villages.

Caution: a brute-force solution that examines every possible set of roads will not finish within the time limit.

Examples3

Example 1

Input

9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0

Expected output

216
30

Example 2
Input
```
2
A 1 B 5
0
```
Expected output
```
5
```
Example 3
Input
```
3
A 2 B 3 C 4
B 1 C 5
0
```
Expected output
```
7
```