En IslaGrande hay ~N~ ciudades, identificados con números desde ~1~ hasta ~N~. La red de carreteras consiste de ~N-1~ carreteras bidireccionales, cada una conectando a dos ciudades, y teniendo una longitud fija – un entero positivo. Cada una de estas carreteras fue construida en un punto diferente del tiempo y la red de carreteras está diseñada de una manera tal que existe una ruta entre dos ciudades cualesquiera, la cual es una carretera o pasa a través de otras ciudades usando carreteras. Puesto que el tráfico se ha incrementado en los últimos tiempos, el gobierno está planeando reemplazar las carreteras por autopistas bidireccionales. Las autopistas entre las ciudades serán construidas acorde a las siguientes reglas:

Una autopista será construida solamente entre dos ciudades, entre las cuales ya existía una carretera. La autopista reemplaza a la carretera. Solamente una autopista será construida en un momento del tiempo. Las autopistas serán construidas en el mismo orden que las carreteras fueron construidas (las carreteras se construyeron en momentos diferentes).

Llamaremos “un área” del país a cualquier subconjunto máximo de ciudades y carreteras (no autopistas) de la red de carreteras iniciales, tal que entre dos ciudades cualesquiera exista una ruta utilizando carreteras. Después de construir cada autopista, exactamente un área del país se divide en dos áreas (es posible que una o ambas de las nuevas áreas consistan de un solo pueblo sin rutas). Una “ruta simple” es una ruta, la cual puede pasar a través de un pueblo a los sumo una vez. Después de construir cada nueva autopista, al gobierno de IslaGrande le gustaría saber las longitudes de la ruta simple más largas entre dos ciudades en cada una de las dos nuevas áreas.

Hacer un programa que permita:

Leer desde la consola la cantidad de ciudades y la red de carreteras existentes antes de la construcción de las autopistas. Después de construir cada autopista encontrar las longitudes de la ruta simple más larga entre dos ciudades en cada una de las dos nuevas áreas. Escribir hacia la consola los valores de las rutas más largas de las dos nuevas áreas cada vez que se construya una autopista.

Entrada

Linea 1: ~N~, representa la cantidad de ciudades.

Linea ~2~..~N~: En cada línea, aparecen tres enteros positivos separados entre sí por un espacio en blanco. Los dos primeros corresponden a la identificación de las dos ciudades entre las cuales hay una carretera y el tercero es la longitud de esa carretera. Las carreteras aparecen en el mismo orden que se construyeron.

Salida

La salida contiene ~N-1~ líneas. En la i-ésima línea se deben escribir dos enteros separados entre sí por un espacio en blanco, los cuales representan las longitudes de las rutas más largas (usando solamente carreteras) entre dos ciudades en cada una de las dos nuevas áreas que se forman después de construir la i-ésima autopista. Escriba los dos enteros en orden creciente.

Restricciones

~1 \leq N \leq 500 000~. Las longitudes de todas las carreteras están entre ~1~ y ~1000~ inclusive.

Ejemplo de entrada

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

Ejemplo de Salida

3 3
0 2
0 0
0 0

Explicación del Ejemplo

1. Antes de construir la primera autopista solamente existe un área formada por todas las ciudades ~{1, 2, 3, 4, 5}~.

2. Después de construir la primera autopista entre las ciudades ~1~ y ~2~ el país se divide en dos áreas ~{1, 5}~ y ~{2, 3, 4}~. La longitud de la ruta más larga entre dos ciudades en cada una de las áreas es: en el área ~{1, 5}~ es de ~3~ entre las ciudades ~1~ y ~5~, en el área ~{2, 3, 4}~ es de ~3~ entre las ciudades ~3~ y ~4~.

3. Después de construir la segunda autopista entre las ciudades ~2~ y ~3~ el área ~{2, 3, 4}~ se divide en dos áreas ~{3}~ y ~{2, 4}~. La longitud de la ruta más larga en ambas áreas es de ~0~ y ~2~ respectivamente.

4. Después de construir la tercera autopista entre las ciudades ~2~ y ~4~. El área ~{2, 4}~ se divide en dos áreas ~{2}~ y ~{4}~. La longitud de la ruta más larga en ambas áreas es ~0~.

5. Después de construir de la cuarta autopista entre las ciudades ~1~ y ~5~. El área ~{1, 5}~ se divide en dos áreas ~{1}~ y ~{5}~. La longitud de las dos rutas más largas es ~0~.