Description

After the incident involving the Prince of Taiping, Lu Xiaofeng was appointed as the Imperial First-Class Guard by the emperor.

The palace layout, starting from the Meridian Gate and extending to the living quarters of the imperial concubines, forms a tree structure, where certain palaces can be seen from one another. The imperial guards are stationed with strict security measures—guards every few steps—and each palace must be monitored around the clock, with varying costs for stationing guards in different palaces.

However, Lu Xiaofeng's budget is insufficient, making it impossible to station guards in every palace.

Help Lu Xiaofeng arrange the guards such that all palaces are monitored while minimizing the total cost.

Input Format

The input describes a tree as follows:

The first line contains an integer $n$, representing the number of nodes in the tree.

The second to the $(n+1)$-th lines describe each palace node, in order: the node's label $i\ (0<i\le n)$, the cost $k$ to station a guard at this palace, the number of children $m$, followed by $m$ numbers representing the labels of the node's children $r_1,r_2,\cdots ,r_m$.

For a tree with $n$ nodes, the node labels range from $1$ to $n$, and no label is repeated.

Output Format

Output the minimum total cost.

Sample 1

The arrangement of guards in six regions is shown in the left diagram.

In the right diagram, gray dots represent stationed guards. Guard $2$ can monitor $1,2,5,6$, guard $3$ can monitor $1,3$, and guard $4$ can monitor $1,4$.

Total cost: $16+5+4=25$

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

25

Data Range and Hint

For $100\%$ of the data, $0 \lt n\le 1500$.