Стаціонарна телефонна мережа#7531
Мер міста RMR хоче створити безпечну телефонну мережу, яка буде використовуватися в екстрених ситуаціях, коли місто буде відрізане від зовнішнього світу. Деякі пари будівель у місті можуть бути безпосередньо з'єднані телефонним проводом. Інженери муніципалітету підготували оцінку вартості підключення для кожної такої пари.
Мерові потрібна ваша допомога: необхідно побудувати найдешевшу мережу, яка з'єднає всі будівлі в місті та при цьому задовольнить вимогам безпеки, викладеним нижче. Дзвінок з будівлі в будівлю повинен проходити простим шляхом (тобто шляхом, що не містить повторюваних будівель). Серед усіх будівель є кілька небезпечних, в яких проживають люди з кримінальним минулим. Мер хоче, щоб до таких будівель був тільки доступ з мережі, але не навпаки. Іншими словами, жодне з'єднання між будівлями та не повинно проходити через небезпечну будівлю (де відмінне від і ).
Перша строка містить три цілих числа n, m, p, де n~(1 \le n \le 1000) — кількість будівель, m~(0 \le m \le 10^5) — кількість можливих прямих з'єднань між парами будівель, а p~(0 \le p \le n) — кількість небезпечних будівель. Будівлі пронумеровані від до .
Друга строка містить різних цілих чисел від до включно — номери небезпечних будівель.
Кожна з наступних строк містить три цілих числа x_i, y_i і l_i, що описують одне потенційне пряме з'єднання: x_i і y_i~(1 \le x_i, y_i \le n) — різні номери будівель, які з'єднуються, а l_i~(1 \le l_i \le 10000) — вартість такого з'єднання.
Між будь-якою парою будівель існує не більше одного прямого з'єднання.
Виведіть вартість найдешевшої мережі, що задовольняє умови безпеки, якщо це можливо. Якщо побудувати таку мережу неможливо, виведіть "impossible".
Приклад 1
Приклад 2