Сортировка червоточин
Сортировка червоточин
Коровы Фермера Джона устали от ежедневных сортировок перед выходом из амбара. Они получили звание "доктор наук" по квантовой физике и готовы ускорить этот процесс.
Этим утром, как обычно 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 обмениваются позициями используя третий туннель.
4 4 3 2 1 4 1 2 9 1 3 7 2 3 10 2 4 3
9
4 1 1 2 3 4 4 2 13
-1