Informatyzacja kraju
Rząd ma ambitny plan informatyzacji kraju. W tym celu zamierza połączyć wszystkie miasta siecią szkieletową, oczywiście jak najmniejszym kosztem. Dodatkowo część kosztów chce przerzucić na samorządy lokalne. Kraj podzielony jest na województwa, z których każde składa się z miasta wojewódzkiego i pewnej liczby pozostałych miast. Rząd zamierza połączyć siecią wszystkie miasta wojewódzkie (podłączenie pozostałych miast pozostawiając samorządom). Połączenie między miastem wojewódzkim A i miastem wojewódzkim B może przechodzić co najwyżej przez jedno miasto niewojewódzkie z województwa A oraz co najwyżej jedno miasto niewojewódzkie z województwa B.
Należy wyznaczyć najmniejszy koszt połączenia wszystkich miast wojewódzkich siecią szkieletową.
Wejście
W pierwszej linii pojawi się n – liczba miast. W kolejnych n liniach pojawią się opisy krawędzi wychodzących z i-tego miasta w formacie:
m c1 d1 ... cm dm
gdzie:
m opisuje liczbą krawędzi wychodzących z i-tego wierzchołka,
cj opisuje cel (miasto) j-tej krawędzi,
dj opisuje koszt j-tej krawędzi (koszt połączenia siecią miast i oraz ci).
Po opisie grafu pojawi się m – liczba województw oraz m ich opisów w postaci:
c k d1 ... dk
gdzie:
c numer miasta wojewódzkiego,
k opisuje liczbę pozostałych miast w województwie,
di to numer i-tego miasta w województwie.
Wyjście
Należy wypisać łączny koszt połączenia wszystkich województw w sieć.
Przykład
Wejście
4
1 1 1
2 0 1 3 4
1 3 2
2 1 4 2 2
2
1 1 0
3 1 2

Wyjście
4