Сортування червоточин
Фермер Джон вирішив полегшити життя своїм коровам, які втомилися від щоденних сортувань перед виходом з амбару. Завдяки своїм знанням у квантовій фізиці, корови готові прискорити цей процес.
Сьогодні вранці 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 обмінюються позиціями через третій тунель.