e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

2020 USACO January Silver

Сортировка червоточин

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

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

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

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

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

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

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

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

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

Пример

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

  • Коровы 1 и 2 обмениваются позициями используя третий туннель.
  • Коровы 1 и 3 обмениваются позициями используя первый туннель.
  • Коровы 2 и 3 обмениваются позициями используя третий туннель.
Ліміт часу 2 секунди
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3
Вихідні дані #1
9
Вхідні дані #2
4 1
1 2 3 4
4 2 13
Вихідні дані #2
-1
Джерело 2020 USACO January Silver