Minimizing Total Time in an RPG Game

In this problem, you are given an RPG game modeled as a directed tree with N narrative points numbered from 1 to N. The game starts at narrative point 1. At each narrative point i, there are K_i branches. Each branch represents a choice that leads to a different subsequent narrative point. If K_i = 0, then the narrative point i is an ending.

When JYY watches a branch (i.e. follows a branch from one narrative point to another), it takes a specified amount of time. Because the narrative is irreversible, once you take a branch you cannot go back to a previously visited narrative point – the only way to return to the beginning is to exit the current game and start a new one (i.e. return to narrative point 1). JYY may exit at any time and restart, but he dislikes having to re-watch previously seen story segments.

Your task is to help JYY cover all branch storylines (i.e. every branch in the tree) while minimizing the total time spent. Formally, let the cost (or time) associated with an edge (branch) be given by t. A playthrough is a simple path starting from narrative point 1 and following a sequence of edges until an ending is reached. Since the game forces you to follow a single branch at each narrative point, if a narrative point has more than one branch, you can cover one branch within a given playthrough for free, but the remaining branches will require you to restart at the beginning and traverse the common prefix again.

The optimal strategy is to choose a set of playthroughs such that each branch is watched exactly once, and the total time is minimized. A key observation is that if a narrative point i (with distance d(i) from the start) has K_i branches, you can cover one branch in a playthrough that already reaches i, whereas the other K_i - 1 branches add an extra cost of d(i) each (because you have to replay the path from the start to i). Therefore, the minimum total time is:

$$\text{answer} = \sum_{\text{edge }(u\to v)} t + \sum_{\text{node }i}\big(K_i - 1\big) \times d(i)$$

where d(i) is the sum of the costs from narrative point 1 to node i along the unique path.

inputFormat

The input begins with a single integer N (N ≥ 1), the total number of narrative points. The following N lines describe each narrative point from 1 to N. Each line starts with an integer K_i (the number of branches available at narrative point i). If K_i > 0, it is followed by 2 × K_i integers. For each branch, a pair of integers is given: the destination narrative point v and the time cost t for watching that branch.

You may assume that the game structure forms a directed tree with narrative point 1 as the root, and every narrative point is reachable from narrative point 1.

outputFormat

Output a single integer, the minimum total time required to watch all branch storylines.

sample

1
0

0