Multi Path Story

Time limit5sMemory limit512 MB

Summary

Given a branching-point DAG where every run restarts at point 1, find the minimum total time to traverse every choice at least once.

Level: Medium7 of 10
Topics: Graph, Shortest path
Solved: No attempts yet

Problem

You are a programmer who loves pretty girl games, a sub-genre of dating simulation games. "Floatable Heart", released last Friday, has just arrived at your home. The game has several stories. When you complete all of them, you get a special figure of the main heroine, Megumi. You want to start playing right away, but first you need to work out how to complete all the stories in the shortest time.

You have a special skill that reveals the branching structure of a game. Using it, you found that the game has $n$ branching points, and the $i$ -th branching point has $k_i$ choices. The game is complicated, so several routes can reach the same $i$ -th branching point. Selecting the $j$ -th choice at the $i$ -th branching point takes $c_{ij}$ minutes to reach another branching point (or an ending).

To complete all the stories, you must select every choice at every branching point and read the story between each branching point and the next one (or an ending). You can assume that a reset back to the beginning, and the trip from the beginning to the first branching point, take negligible time.

The manual says the game has a "Quick Save" feature, which records your current position so you can return to it later. A bug keeps this feature from working. So whenever you reach an ending or quit the game partway, you must restart from the first branching point. No patch for the bug has been released. This is a hard constraint even for the fastest players.

Find the shortest total time needed to complete all the stories.

Input

The input is given in the following format.

n
k1 t11 c11 ... t1k1 c1k1
:
kn tn1 cn1 ... tnkn cnkn

The first line contains the number of branching points $n$ ( $2 \le n \le 1000$ ). The next $n$ lines describe the branching points with IDs $1$ to $n$ . The first integer $k_i$ ( $0 \le k_i \le 50$ ) is the number of choices at branching point $i$ . If $k_i = 0$ , branching point $i$ is an ending. Then come $2k_i$ integers: $t_{ij}$ ( $1 \le t_{ij} \le n$ ) is the ID of the branching point you reach by selecting choice $j$ , and $c_{ij}$ ( $0 \le c_{ij} \le 300$ ) is the time to read the story between branching point $i$ and $t_{ij}$ .

The branching point with ID 1 is the first branching point. Every branching point and ending is reachable from the first branching point. The game has no loops: without a reset, no branching point is reached more than once.

Output

Print the shortest time needed to complete all the stories on a single line.

Examples3

Example 1
Input
```
2
1 2 2
0
```
Expected output
```
2
```

Example 2

Input

Expected output

Example 3

Input

6
3 2 100 3 10 3 10
1 4 100
1 4 10
3 5 1 5 1 6 1
0
0

Expected output