Minimizing Total Time to Watch All Branches in an RPG Game

JYY is an ardent RPG fan who wishes to experience every side narrative in his newly purchased game in the least amount of time. The game consists of \(n\) story points, numbered from 1 to \(n\). At the \(i\)-th story point, there are \(k_i\) possible outgoing branches. Each branch leads to a new story point and requires a certain amount of time to watch. If \(k_i=0\), it means that the \(i\)-th story point is an ending.

The game has a special mechanism: starting at story point 1, the path from the start to any story point is unique (i.e. the structure forms a tree), and every story point is reachable from point 1. Moreover, at any story point, JYY can perform a "save" operation to record his progress, and later, he can "load" this save to return instantly to that saved point. There is only one save slot, so every new save overwrites the previous one. Additionally, JYY can restart the game (return to story point 1) at any time, all without any time cost.

Because rewatching already-viewed narratives is painful, JYY wants to watch each unique branch exactly once while minimizing the total time spent. With optimal use of the save/load and restart features, the optimal strategy allows JYY to experience every branch exactly once. Hence, the minimum total time is the sum of the time costs on all the branches, i.e., \(\sum_{\text{edge}\,\in\,T} t_{edge}\).

Your task is to compute this minimum total time.

inputFormat

The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)), representing the number of story points.

Then, \(n\) lines follow. The \(i\)-th line describes the \(i\)-th story point. It starts with an integer \(k_i\) (\(0 \leq k_i \leq 10\)); if \(k_i>0\), then it is followed by \(k_i\) pairs of integers. Each pair \(v\) and \(t\) indicates that one branch from story point \(i\) leads to story point \(v\) with time cost \(t\) (\(1 \leq t \leq 10^4\)). It is guaranteed that the structure forms a tree rooted at 1.

outputFormat

Output a single integer: the minimum total time required for JYY to watch all the side narratives.

sample

3
1 2 5
1 3 10
0

15