Коровы Фермера Джона устали от ежедневных сортировок перед выходом из амбара. Они получили звание "доктор наук" по квантовой физике и готовы ускорить этот процесс.

Этим утром, как обычно n коров, последовательно пронумерованных от 1 до n, находятся в амбаре на различных позициях, также пронумерованных от 1 до n, так что корова i находится в позиции pi. Однако этим утром появились m туннелей, пронумерованных от 1 до m, при этом туннель i двунаправленно связывает позиции ai и bi и имеет ширину wi.

В любой момент времени две коровы, расположенные на противоположных концах туннеля могут параллельно поменяться позициями через него. Коровы могут таким образом меняться позициями сколько угодно раз пока корова i не окажется в позиции i для 1 ≤ i ≤ n.

Коровы не хотят быть раздавленными в туннелях. Помогите им максимизировать ширину туннеля с самой маленькой шириной, которые они должны использовать, чтобы упорядочиться

Входные данные

Первая строка содержит два целых числа n (1 ≤ n ≤ 105) и m (1 ≤ m ≤ 105). Вторая строка содержит n целых чисел p1, p2,..., pn. Гарантируется, что p есть перестановка чисел от 1 до n.

Для каждого i между 1 и m, строка i + 2 содержит целые числа ai, bi и wi (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ wi ≤ 109).

Выходные данные

Выведите одно целое число - наибольшую минимальную ширину туннеля, в которую поместятся коровы во время сортировки. Если коровы не используют туннели во время сортировки, выведите -1.

Пример

Имеется единственный вариант отсортировать коров, используя туннели с минимальной шириной 9.

• Коровы 1 и 2 обмениваются позициями используя третий туннель.
• Коровы 1 и 3 обмениваются позициями используя первый туннель.
• Коровы 2 и 3 обмениваются позициями используя третий туннель.