题目描述

宅男 JYY 非常喜欢玩 RPG 游戏，并且 JYY 总是想花费最少的时间看完所有的支线剧情。最近JYY买了一款新的正版 RPG 游戏,所以 JYY 总算可以“读档”和“存档”了！

JYY 现在所玩的 RPG 游戏中，一共有 $n$ 个剧情点，由 $1$ 到 $n$ 编号，第 $i$ 个剧情点可以根据 JYY 的不同的选择，而经过不同的支线剧情，前往 $k_i$ 种不同的新的剧情点。当然如果 $k_i$ 为 $0$，则说明 $i$ 号剧情点是游戏的一个结局了。

JYY 观看一个支线剧情需要一定的时间。JYY—开始处在 $1$ 号剧情点，也就是游戏的开始。JYY 买的这款游戏很特殊，从游戏开始到达任何一个剧情点的支线路径都是唯一的。而且，任何一个剧情点都是从 $1$ 号剧情点可达的。

与上一款 RPG 游戏一样，JYY 可以在任意时刻选择重新开始游戏，即回到 $1$ 号剧情点。不过有些不同的是，这次 JYY 买的是正版软件，每当 JYY 到达一个剧情点，JYY 都可以进行“存档”和“读档”。但是很遗憾的是，JYY 的 RPG 游戏只有一个存档的位置：每次“存档”操作都会覆盖之前的存档。比如，如果 JYY 在 $x$ 号剧情点进行了“存档”操作，那么此后当 JYY 到达任何一个剧情点（包括结局）都可以“读档”并立即回到 $x$号剧情点。但是如果之后 JYY 在 $y$ 号剧情点又进行了“存档”，那么 JYY 再进行“读档”，就只能回到 $y$ 号剧情点了。

一开始存档位置里没有存储任何信息，所以 JYY 只有在进行一次“存档”操作之后才可以进行“读档”操作，并且“读档”，“存档”和“重新开始”都是不需要花费时间的。

重复观看己经看过的剧情是很痛苦的，JYY 希望花费最少的时间，看完所有不同的支线剧情。

输入格式

第一行为一个正整数 $n$。

接下来 $n$ 行，第 $i$ 行为第 $i$ 号剧情点的信息。

每一行第一个非负整数为 $k_i$。接下来 $k_i$ 个整数对，$b_{i,j}$ 和 $t_{i,j}$，表示从剧情点 $i$ 可以前往剧情点 $b_{i,j}$，并且观看这段支线剧情需要花费 $t_{i,j}$ 的时间。

输出格式

一行一个整数，表示 JYY 看完所有支线剧情所需要的最少时间。

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

提示

样例解释 1

最佳路线为：

从 $1$ 前往 $5$，然后重新开始。

从 $1$ 前往 $2$，在 $2$ 处存档，再前往 $6$，并读档。

从 $2$ 前往 $3$，在 $3$ 处存档，再前往 $7$，并读档。

从 $3$ 前往 $4$，在 $4$ 处存档，再前往 $8$，并读档。

最后前往 $9$，花费时间为 $8$。可以证明没有比 $8$ 更小的答案。

数据范围

对于 $100\%$ 的数据，$n\leq 10^6,1\leq t_{i,j}\leq 10^4,\sum\limits_{i=1}^{n}k_i=n-1$。