Camino máximo P13664

Un país tiene $n$ ciudades conectadas por carreteras bidireccionales. Se sabe que, para cada par de ciudades $x$ e $y$, existe exactamente una manera de ir de $x$ a $y$ sin pasar más de una vez por la misma ciudad. Cada carretera tiene una cierta longitud. Calculad el camino de longitud máxima que no repite ninguna ciudad.

Entrada

Una entrada consiste en como mucho 10 casos. Cada caso comienza con el número de ciudades $n \le 10^5$, seguido de $n - 1$ líneas con información de cada carretera: las dos ciudades conectadas directamente y la longitud de la carretera, que está siempre entre 1 y 1000. Las ciudades se numeran de 1 a $n$. Ninguna entrada será mayor de 2 Mb.

Salida

Para cada caso, escribid en una línea la longitud del camino más largo. Vuestro programa dispone de un segundo de CPU para resolver todos los casos de una entrada.

Puntuación

• TestA:

  Casos con $1 \le n \le 3$

• TestB:

  Casos con $1 \le n \le 100$

• TestC:

  Casos con $1 \le n \le 10^5$ y donde no existen caminos de más de 1000 pasos.

• TestD:

  Casos con $1 \le n \le 10^5$.