Description

The otaku JYY really likes playing RPG games, and JYY always wants to spend the least time to watch all side plots. Recently, JYY bought a new genuine RPG game, so JYY can finally “load” and “save”!

In the RPG game JYY is playing now, there are $n$ plot points, numbered from $1$ to $n$. At plot point $i$, depending on JYY’s choices, JYY may go through different side plots and reach $k_i$ different new plot points. Of course, if $k_i$ is $0$, it means that plot point $i$ is an ending of the game.

Watching a side plot takes some time. JYY starts at plot point $1$, which is the beginning of the game. This game is special: from the beginning to any plot point, the side-plot path is unique. Also, every plot point is reachable from plot point $1$.

Just like in the previous RPG game, JYY can choose to restart the game at any time, i.e. return to plot point $1$. However, something is different this time: since JYY bought the genuine software, whenever JYY reaches a plot point, JYY can “save” and “load”. Unfortunately, this RPG game has only one save slot: each “save” operation overwrites the previous save. For example, if JYY performs “save” at plot point $x$, then afterward, when JYY reaches any plot point (including an ending), JYY can “load” and immediately return to plot point $x$. But if later JYY performs “save” at plot point $y$, then when JYY “loads” again, JYY can only return to plot point $y$.

At the beginning, the save slot stores no information, so JYY can only “load” after performing a “save” at least once. Also, “load”, “save”, and “restart” take no time.

Rewatching plots that have already been watched is very painful. JYY wants to spend the least time to watch all different side plots.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines describe the information of plot points. Line $i$ describes plot point $i$.

In each line, the first non-negative integer is $k_i$. Then follow $k_i$ pairs of integers $b_{i,j}$ and $t_{i,j}$, meaning that from plot point $i$ one can go to plot point $b_{i,j}$, and watching this side plot takes $t_{i,j}$ time.

Output Format

Output one integer in one line, the minimum time required for JYY to finish watching all side plots.

9
2 5 1 2 1
2 3 1 6 1
2 7 1 4 1
2 8 1 9 1
0
0
0
0
0

8

Hint

Sample Explanation 1

The best route is:

Go from $1$ to $5$, then restart.

Go from $1$ to $2$, save at $2$, then go to $6$, and load.

Go from $2$ to $3$, save at $3$, then go to $7$, and load.

Go from $3$ to $4$, save at $4$, then go to $8$, and load.

Finally go to $9$. The total time is $8$. It can be proven that there is no answer smaller than $8$.

Constraints

For $100\%$ of the testdata, $n\leq 10^6$, $1\leq t_{i,j}\leq 10^4$, $\sum\limits_{i=1}^{n}k_i=n-1$.

Translated by ChatGPT 5