CSES - Etäisyydet
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Sinulle on annettu tiedot nn 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 nn: kaupunkien määrä. Kaupungit on numeroitu 1,2,,n1,2,\ldots,n.

Sitten syötteessä on n1n-1 riviä, jotka kuvaavat tiet. Jokaisella rivillä on kolme kokonaislukua aa, bb ja cc: kaupunkien aa ja bb välillä on tie, jonka pituus on cc. Kaikki tiet ovat kaksisuuntaisia.

Tuloste

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

Rajat

  • 1n1051 \le n \le 10^5
  • 1a,bn1 \le a,b \le n
  • 1c1091 \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