В большом городе оператор сотовой связи проводит конкурс для абонентов для продвижения своей новой услуги "пешеходный навигатор". Главный приз будет присужден первой паре абонентов, которые встретятся друг с другом. Конкурс завершается, когда любая такая встреча состоится.
В начале конкурса все абоненты находятся на своих позициях. Известно, что они способны видеть друг друга на своих смартфонах, и двигаются с постоянной скоростью 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) километров.
Вывести наименьшее возможное количество минут, через которое может завершится соревнование. Гарантируется, что как минимум одна пара абонентов встретится.