eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Відстань

Відстань

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

У великому місті оператор стільникового зв'язку проводить конкурс для абонентів з метою популяризації своєї нової послуги "пішоходний навігатор". Головний приз буде присуджено першій парі абонентів, які зустрінуться один з одним. Конкурс завершується, коли довільна така зустріч відбудеться.

На початку конкурсу усі абоненти знаходяться на своїх позиціях. Відомо, що вони здатні бачити один одного на своїх смартфонах, і рухаються з постійною швидкістю 10 км/год лише пішки. Кожен абонент бажає виграти приз і байдужий до інших.

Для підготовки до церемонії нагородження оператор стільникового зв'язку повинен знати найменший проміжок часу, після якого завершиться змагання.

Вхідні дані

Перший рядок містить три цілих числа N, K і L - кількість абонентів у стільниковій компанії (2N10^5), кількість вузлів (1K10^5) та кількість пішоходних прогулянок (1L10^5) у місті відповідно.

У наступних N вхідних рядках міститься S_i (1S_iK) чисел - початкове положення абонентів (у термінах вузлів транспортного графу).

Наступні L рядків описують пішоходні прогулянки у вигляді цілих чисел B_i, C_i та D_i, відокремлені пропуском. Кожен рядок говорить про те, що існує двосторонній шлях між вузлами B_i та C_i (1B_i, C_iK, B_iC_i) довжиною D_i (1D_i5000) кілометрів.

Вихідні дані

Вивести найменшу можливу кількість хвилин, через які може завершитись змагання. Гарантується, що як мінімум одна пара абонентів зустрінеться.

Приклад

Вхідні дані #1
2 2 1
1
2
1 2 5
Вихідні дані #1
15
Джерело ACM ICPC 2010-2011 NEERC Moscow Subregional