Matcom Online Grader

Cierto reino esta conformado por n ciudades. La cuidades están conectadas por n−1 carreteras de forma tal que existe una única forma de viajar entre dos cuidades sin pasar dos veces por un mismo lugar. Un día el rey decidió realizar un recorrido, para ello debe elegir dos ciudades a y b (posiblemente la misma) e ir desde una hacia la otra, pero sin pasar dos veces por el mismo sitio. No obstante cada carretera tiene cierta belleza, por lo que el rey quiere elegir las ciudades de forma tal que la belleza de la ruta recorrida sea máxima.
La belleza de una ruta es el xor de las bellezas de todas las carreteras que la conforman. Tu tarea es ayudarlo a elegir la menor ruta.

Input

La primera línea contine un entero n (1 ≤ n ≤ 500000) — la cantidad de ciudades. Las ciudades están enumeradas desde 1 hasta n. En las siguientes n−1 líneas está la descripción de cada carretera. Esta consiste de tres enteros a, b, c (1 ≤ a,b ≤ n,1 ≤ c ≤ 10^9), indicando las cuidades que conecta directamente la carretera, y la belleza de la misma, respectivamente.

Output

La única lúnea de salida será la belleza máxima de la ruta que seleccionará en rey para su viaje.

Sample test(s)