Відстань
Відстань
У великому місті оператор стільникового зв'язку проводить конкурс для абонентів з метою популяризації своєї нової послуги "пішоходний навігатор". Головний приз буде присуджено першій парі абонентів, які зустрінуться один з одним. Конкурс завершується, коли довільна така зустріч відбудеться.
На початку конкурсу усі абоненти знаходяться на своїх позиціях. Відомо, що вони здатні бачити один одного на своїх смартфонах, і рухаються з постійною швидкістю 10 км/год лише пішки. Кожен абонент бажає виграти приз і байдужий до інших.
Для підготовки до церемонії нагородження оператор стільникового зв'язку повинен знати найменший проміжок часу, після якого завершиться змагання.
Вхідні дані
Перший рядок містить три цілих числа N, K і L - кількість абонентів у стільниковій компанії (2 ≤ N ≤ 10^5), кількість вузлів (1 ≤ K ≤ 10^5) та кількість пішоходних прогулянок (1 ≤ L ≤ 10^5) у місті відповідно.
У наступних N вхідних рядках міститься S_i (1 ≤ S_i ≤ K) чисел - початкове положення абонентів (у термінах вузлів транспортного графу).
Наступні L рядків описують пішоходні прогулянки у вигляді цілих чисел B_i, C_i та D_i, відокремлені пропуском. Кожен рядок говорить про те, що існує двосторонній шлях між вузлами B_i та C_i (1 ≤ B_i, C_i ≤ K, B_i ≠ C_i) довжиною D_i (1 ≤ D_i ≤ 5000) кілометрів.
Вихідні дані
Вивести найменшу можливу кількість хвилин, через які може завершитись змагання. Гарантується, що як мінімум одна пара абонентів зустрінеться.
Приклад
2 2 1 1 2 1 2 5
15