Las vacas del Granjero Juan se han cansado de su pedido diario de que ellas se ordenen antes de dejar el establo cada mañana. Ellas acaban de completar sus doctorados en fisica cuantica, y estan listas a acelerar un poco las cosas. Esta mañana, como es usual, las ~N~ vacas del Granjero Juan ~(1 \leq N \leq 10^5)~, convenientemente numeradas ~1...N~, estan acantonadas en el establo en ~N~ posiciones distintas, tambien numeradas ~1...N~, de tal manera que la vaca ~i~ esta en la posicion ~p_i~. Pero esta mañana también hay ~M~ agujeros de gusano ~(1 \leq M \leq 10^5)~, numeradas ~1...M~, donde el agujero de gusano ~i~ conecta bidireccionalmente la posicion ~a_i~ con la posicion ~b_i~ y tiene ancho ~w_i~ ~(1 \leq a_i, b_i \leq N~, ~a_i \neq b_i~, ~1 \leq w_i \leq 10^9~.

En cualquier momento, dos vacas situadas en extremos opuestos de un agujero de gusano pueden optar por intercambiar simultáneamente sus lugares a través del agujero de gusano. Las vacas deben realizar dichos intercambios hasta que la vaca ~i~ esté en la ubicación ~i~ para ~1 \leq i \leq N~.

Las vacas no quieren ser aplastadas por los agujeros de gusano. Ayúdales a maximizar la anchura del agujero de gusano menos ancho que deben utilizar para ordenarse. Se garantiza que es posible que las vacas se ordenen a sí mismas.

Entrada

La primera línea contiene dos enteros, ~N~ y ~M~. La segunda línea contiene los ~N~ enteros ~p1,p2,...,pN~. Se garantiza que ~p~ es una permutación de ~1...N~.

Para cada ~i~ entre 1 y ~M~, la línea ~i+2~ contiene los enteros ~a_i, b_i~ y ~w_i~.

Salida

Un único número entero: la máxima anchura mínima de los agujeros de gusano en los que debe meterse una vaca durante el proceso de clasificación. Si las vacas no necesitan ningún agujero de gusano para clasificarse, la salida es -1.

Ejemplo #1 de Entrada

4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3

Ejemplo #1 de Salida

9

Esta es una forma posible de ordenar las vacas utilizando sólo agujeros de gusano de una anchura mínima de 9:

La vaca 1 y la vaca 2 intercambian sus posiciones utilizando el tercer agujero de gusano. La vaca 1 y la vaca 3 intercambian sus posiciones utilizando el primer agujero de gusano. La vaca 2 y la vaca 3 intercambian sus posiciones utilizando el tercer agujero de gusano.

Ejemplo #2 de Entrada

4 1
1 2 3 4
4 2 13

Ejemplo #2 de Salida

-1

No se necesitan agujeros de gusano para ordenar las vacas.

Calificación

Los casos 3-5 satisfacen ~N,M \leq 1000~. Los casos 6-10 no satisfacen restricciones adicionales.