Сортировка червоточин
Коровы Фермера Джона устали от ежедневных сортировок перед выходом из амбара. Они получили звание "доктор наук" по квантовой физике и готовы ускорить этот процесс.
Этим утром, как обычно n коров, последовательно пронумерованных от 1 до n, находятся в амбаре на различных позициях, также пронумерованных от 1 до n, так что корова i находится в позиции p[i]. Однако этим утром появились m туннелей, пронумерованных от 1 до m, при этом туннель i двунаправленно связывает позиции a[i] и b[i] и имеет ширину w[i].
В любой момент времени две коровы, расположенные на противоположных концах туннеля могут параллельно поменяться позициями через него. Коровы могут таким образом меняться позициями сколько угодно раз пока корова i не окажется в позиции i для 1 ≤ i ≤ n.
Коровы не хотят быть раздавленными в туннелях. Помогите им максимизировать ширину туннеля с самой маленькой шириной, которые они должны использовать, чтобы упорядочиться
Входные данные
Первая строка содержит два целых числа n (1 ≤ n ≤ 10^5) и m (1 ≤ m ≤ 10^5). Вторая строка содержит n целых чисел p[1], p[2],..., p[n]. Гарантируется, что p есть перестановка чисел от 1 до n.
Для каждого i между 1 и m, строка i + 2 содержит целые числа a[i], b[i] и w[i] (1 ≤ a[i], b[i] ≤ n, a[i] ≠ b[i], 1 ≤ w[i] ≤ 10^9).
Выходные данные
Выведите одно целое число - наибольшую минимальную ширину туннеля, в которую поместятся коровы во время сортировки. Если коровы не используют туннели во время сортировки, выведите -1.
Пример
Имеется единственный вариант отсортировать коров, используя туннели с минимальной шириной 9.
Коровы 1 и 2 обмениваются позициями используя третий туннель.
Коровы 1 и 3 обмениваются позициями используя первый туннель.
Коровы 2 и 3 обмениваются позициями используя третий туннель.