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