Matcom Online Grader

La compañía de aviación de Ryan ofrece sus servicios en $N$ ciudades importantes del mundo. Se enorgullece sobremanera de la calidad de sus ofertas y de sus precios tan bajos.

Actualmente ofrece $N-1$ vuelos de forma tal que se puede viajar entre todo par de ciudades tomando varios de ellos. El próximo plan de la compañía es crear un vuelo directo entre todo par de ciudades que no tengan uno hasta el momento. Uno de los objetivos es mantener los precios bajos y por tanto se quiere que la suma de los precios de todos los vuelos sea mínima, aunque en ningún caso el precio de un vuelo ya existente se modificará. Una restricción importante, que piensa cumplir la empresa, para evitar que los precios bajen demasiado, es escoger estos de forma tal que todo subconjunto de $N - 1$ vuelos, donde al menos uno de ellos es nuevo y que permita viajar entre cualquier par de ciudades ha de tener una suma de precios mayor que la suma de los precios de los vuelos actuales.

La primera línea de la entrada es un entero $N$ $(2 \leq N \leq 100000)$ que indica la cantidad de ciudades. Las siguientes $N - 1$ líneas describen los vuelos que ofrece la compañía en estos momentos. Cada vuelo se describe con tres enteros $A$ $(1 \leq A \leq N)$, $B$ $(1 \leq B \leq N)$ y $C$  $(0 \leq C \leq 10000)$ que representan respectivamente las ciudades que conecta y el costo del pasaje. Todos los precios son enteros, incluidos los de aquellos que piensan agregarse.

La salida debe ser un número entero que representa la menor suma de los precios de todos los vuelos teniendo en cuenta las restricciones planteadas.