CSES - Riita
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Uolevi ja Maija olivat kauan ystäviä, mutta sitten heille tuli riita. He haluavat muuttaa asumaan kahteen kaupunkiin niin, että kaupunkien etäisyys on mahdollisimman suuri.

Kaupunkeja on nn, ja niiden välillä on joukko teitä niin, että jokaisen kahden kaupungin välillä on yksikäsitteinen reitti.

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 yksi kokonaisluku: pisin mahdollinen etäisyys kaupunkien välillä.

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:

15