== include(page="template/taskheader" task_id="sushi2") ==
După o zi productivă de făcut curăţenie, Henry şi Hetty au ieşit în oraş la un restaurant de sushi. În acest restaurant există N mese unite între ele prin N-1 benzi rulante cu dublu sens, astfel încât oricare două mese sunt conectate direct sau indirect prin benzi rulante. Pentru fiecare masă i, $1 ≤ i ≤ N$, cunoaştem atât numărul Ki de mese cu care este conectată direct, cât şi lista ordonată de mese vecine acesteia: Vi,1, Vi,2 … Vi,Ki. Benzile rulante au rolul de a transporta preparatele la clienţi. Acestea urmează un traseu unic, definit după următoarea regulă: pentru orice masă i, un preparat aflat la masa i care tocmai a venit dinspre masa Vi,j, va pleca de la masa i spre masa:
* Vi,j+1, dacă 1 ≤ j < Ki
* Vi,1, dacă j = Ki.
În plus, dacă un preparat nou este trimis de la masa 1 spre masa V1,1, ştim că acesta va ajunge la masa i pentru prima oară venind dinspre masa Vi,1, pentru orice i, 1 ≤ i ≤ N.
După o zi productivă de făcut curăţenie, Henry şi Hetty au ieşit în oraş la un restaurant de sushi. În acest restaurant există N mese unite între ele prin N-1 benzi rulante cu dublu sens, astfel încât oricare două mese sunt conectate direct sau indirect prin benzi rulante. Pentru fiecare masă i, $1 ≤ i ≤ N$, cunoaştem atât numărul K ~i~ de mese cu care este conectată direct, cât şi lista ordonată de mese vecine acesteia: V ~i,1~ , V ~i,2~ … V ~i,Ki~ . Benzile rulante au rolul de a transporta preparatele la clienţi. Acestea urmează un traseu unic, definit după următoarea regulă: pentru orice masă i, un preparat aflat la masa i care tocmai a venit dinspre masa V ~i,j~ , va pleca de la masa i spre masa:
* V ~i,j+1~ , dacă $1 ≤ j < K ~i~$
* V ~i,1~ , dacă $j = K ~i~$.
În plus, dacă un preparat nou este trimis de la masa 1 spre masa V ~1,1~ , ştim că acesta va ajunge la masa i pentru prima oară venind dinspre masa V ~i,1~ , pentru orice i, $1 ≤ i ≤ N$.
h2. Cerinta
Henry şi Hetty au intrat în restaurant la momentul de timp 0. Ei ştiu că pe parcursul vizitei lor pe benzile rulante vor fi aşezate M preparate. Pentru fiecare din cele M preparate ei cunosc tripletul (x, y, t), semnificând faptul că la momentul de timp t preparatul va fi aşezat pe bandă în dreptul mesei x pentru a pleca spre spre masa Vx,y. Ei mai ştiu şi că timpul necesar unui preparat de a parcurge distanţa dintre două mese vecine este de o unitate. Cei doi se vor aşeza la o masă şi vor lua de pe bandă toate preparatele care trec prin dreptul mesei respective. Henry şi Hetty se întreabă: pentru fiecare masă i, care este timpul minim după care culeg toate cele M preparate ce vor fi puse pe bandă?
Henry şi Hetty au intrat în restaurant la momentul de timp 0. Ei ştiu că pe parcursul vizitei lor pe benzile rulante vor fi aşezate M preparate. Pentru fiecare din cele M preparate ei cunosc tripletul $(x, y, t)$, semnificând faptul că la momentul de timp t preparatul va fi aşezat pe bandă în dreptul mesei x pentru a pleca spre spre masa V ~x,y~ . Ei mai ştiu şi că timpul necesar unui preparat de a parcurge distanţa dintre două mese vecine este de o unitate. Cei doi se vor aşeza la o masă şi vor lua de pe bandă toate preparatele care trec prin dreptul mesei respective. Henry şi Hetty se întreabă: pentru fiecare masă i, care este timpul minim după care culeg toate cele M preparate ce vor fi puse pe bandă?
h2. Date de intrare
Pe prima linie a fişierului de intrare sushi.in se vor afla două numere naturale N şi M, reprezentând numărul de mese, respectiv numarul de preparate aflate în restaurant. Pe următoarele N linii se vor afla descrierile listelor de vecini ale fiecărei mese. Aftfel, pe linia i+1, se va afla numărul natural Ki, urmat de Ki numere naturale: Vi,1, Vi,2 … Vi,Ki, cu semnificaţia din enunţ. Pe fiecare din următoarele M linii se va afla cate un triplet de numere naturale (x, y, t), semnificând faptul că la momentul de timp t un preparat va fi aşezat pe bandă în dreptul mesei x pentru a pleca spre masa Vx,y.
Pe prima linie a fişierului de intrare $sushi2.in$ se vor afla două numere naturale N şi M, reprezentând numărul de mese, respectiv numarul de preparate aflate în restaurant. Pe următoarele N linii se vor afla descrierile listelor de vecini ale fiecărei mese. Aftfel, pe linia i + 1, se va afla numărul natural K ~i~ , urmat de K ~i~ numere naturale: V ~i,1~ , V ~i, 2~ … V ~i,Ki~ , cu semnificaţia din enunţ. Pe fiecare din următoarele M linii se va afla cate un triplet de numere naturale $(x, y, t)$, semnificând faptul că la momentul de timp t un preparat va fi aşezat pe bandă în dreptul mesei x pentru a pleca spre masa V ~x,y~ .
h2. Date de ieşire
