Sinulle on annettu tiedot n kaupungista ja niiden välisistä teistä. Jokaisen kahden kaupungin välillä on yksikäsitteinen reitti. Tehtäväsi on selvittää, mikä on suurin etäisyys jokaisesta kaupungista toiseen kaupunkiin.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: kaupunkien määrä. Kaupungit on numeroitu 1,2,\ldots,n.

Sitten syötteessä on n-1 riviä, jotka kuvaavat tiet. Jokaisella rivillä on kolme kokonaislukua a, b ja c: kaupunkien a ja b välillä on tie, jonka pituus on c. Kaikki tiet ovat kaksisuuntaisia.

Tuloste

Tulosta n kokonaislukua: suurin etäisyys jokaisesta kaupungista toiseen kaupunkiin.

Rajat

• 1 \le n \le 10^5
• 1 \le a,b \le n
• 1 \le c \le 10^9

Esimerkki

Syöte:

5
1 2 3
2 3 5
2 4 2
1 5 7

Tuloste:

8 10 15 12 15