다중 경로 스토리

당신은 미소녀 게임(연애 시뮬레이션 게임의 하위 장르)을 좋아하는 프로그래머다. 지난 금요일에 발매된 "Floatable Heart"가 방금 집에 도착했다. 이 게임에는 여러 개의 스토리가 있고, 모든 스토리를 완료하면 주인공 메구미의 특별한 피규어를 얻을 수 있다. 얼른 게임을 시작하고 싶지만, 먼저 모든 스토리를 가장 짧은 시간에 완료하는 방법부터 생각해 보자.

당신에게는 게임의 분기점 구조를 파악하는 특별한 능력이 있다. 이 능력으로 게임에 분기점이 $n$개 있고, $i$번 분기점에는 선택지가 $k_i$개 있다는 것을 알아냈다. 게임이 복잡해서 여러 경로가 같은 $i$번 분기점에 도달할 수 있다. $i$번 분기점에서 $j$번째 선택지를 고르면 다른 분기점(또는 엔딩)에 도달하는 데 $c_{ij}$분이 걸린다.

모든 스토리를 완료하려면 모든 분기점에서 선택지를 전부 고르고, 분기점과 다음 분기점(또는 엔딩) 사이의 이야기를 모두 읽어야 한다. 처음으로 돌아가는 리셋과 게임 처음부터 첫 번째 분기점까지 진행하는 데 걸리는 시간은 무시할 수 있다고 가정한다.

설명서에 따르면 이 게임에는 현재 위치를 저장해 두었다가 나중에 그 위치로 돌아갈 수 있는 "퀵 세이브" 기능이 있다. 그러나 버그 때문에 이 기능은 작동하지 않는다. 따라서 엔딩에 도달하거나 도중에 게임을 끌 때마다 첫 번째 분기점부터 다시 시작해야 한다. 이 버그를 고치는 패치는 아직 나오지 않았다. 최고 수준의 플레이어에게도 까다로운 조건이다.

모든 스토리를 완료하는 데 걸리는 최단 시간을 구하라.

입력은 다음 형식으로 주어진다.

n
k1 t11 c11 ... t1k1 c1k1
:
kn tn1 cn1 ... tnkn cnkn

첫 줄에는 분기점의 개수 $n$이 주어진다($2 \le n \le 1000$). 다음 $n$개 줄은 ID가 1부터 $n$까지인 분기점을 차례로 설명한다. 첫 번째 정수 $k_i$($0 \le k_i \le 50$)는 $i$번 분기점의 선택지 개수다. $k_i = 0$이면 $i$번 분기점은 엔딩이다. 이어서 $2k_i$개의 정수가 나온다. $t_{ij}$($1 \le t_{ij} \le n$)는 $j$번째 선택지를 골랐을 때 도달하는 분기점의 ID이고, $c_{ij}$($0 \le c_{ij} \le 300$)는 $i$번 분기점에서 $t_{ij}$번 분기점까지의 이야기를 읽는 데 걸리는 시간이다.

ID가 1인 분기점이 첫 번째 분기점이다. 모든 분기점과 엔딩은 첫 번째 분기점에서 도달할 수 있다. 게임에는 순환이 없다. 즉, 리셋 없이 같은 분기점에 두 번 이상 도달하는 경우는 없다.

최단 시간을 한 줄에 출력한다.