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