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