Fişierul intrare/ieşire:	sushi2.in, sushi2.out	Sursă	ONI 2016, clasele 11-12
Autor	Eugenie Daniel Posdarascu, Vlad Gavrila	Adăugată de	Vlad Dumitru-Popescu •depevlad
Timp execuţie pe test	0.4 sec	Limită de memorie	128000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

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ă?

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.

Date de ieşire

Pe prima linie a fişierului de ieşire sushi.out se vor afisa N numere naturale, al i-ulea dintre acestea reprezentând timpul necesar pentru culegerea tuturor preparatelor de pe bandă dacă Henry şi Hetty s-ar aşeza la masa cu indice i.

Restricţii

 1 ≤ N ≤ 100 000
 1 ≤ M ≤ 100 000
 Pentru fiecare triplet (x, y, t) avem 1 ≤ x ≤ N, 1 ≤ y ≤ Kx şi 0 ≤ t ≤ 100 000

Exemplu

Explicaţie

...

Cum se trimit solutii?