Задачі
Стаціонарна телефона мережа
Стаціонарна телефона мережа
Мер міста RMR хоче створити безпечну телефонну мережу для використання в екстрених ситуаціях в разі серйозних лих, коли місто буде відрізане від зовнішнього світу. Деякі пари будівель в місті можуть бути безпосередньо пов'язані телефонним дротом. Інженери муніципалітету підготували оцінку вартості підключення будь-якої такої пари.
Мер потребує Вашої допомоги --- йому слід побудувати найдешевшу мережу, що з'єднує всі будівлі в місті і задовольняє заходам безпеки, які викладені далі. Дзвінок з будівлі $A$ в іншу будівлю $B$ повинен відбуватися по простому шляху (який не містить будівель що повторюються). Існує кілька небезпечних будівель, в яких живуть люди з кримінальною історією. Мер хоче щоб до цих будівель був тільки доступ з мережі. Тобто жодне з'єднання між будівлями $A$ і $B$ не повинно проходити через небезпечне будівлю $C$ в мережі (де $C$ не дорівнює $A$ і $B$ ).
\InputFile
Перший рядок містить три цілих числа $n, m, p$, де $n~(1 \le n \le 1000)$ --- кількість будинків, $m~(0 \le m \le 10^5)$ --- кількість можливих прямих з'єднань між парами будинків, а $p~(0 \le p \le n)$ --- кількість небезпечних будівель. Будинки пронумеровані від $1$ до $n$. Другий рядок містить $p$ різних цілих чисел від $1$ до $n$ (включно) --- номера небезпечних будівель. Кожна з таких $m$ рядків містить три цілих числа $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)$ --- вартість з'єднання цих будівель. Між будь-якими двома містами існує не більше одного прямого з'єднання.
\OutputFile
Виведіть вартість найдешевшої мережі, що задовольняє по можливості умовам безпеки. Інакше виведіть "\textbf{impossible}".
\includegraphics{https://static.e-olymp.com/content/d2/d22330092a2b7d38687dfbd6b7fb73997f1275ef.gif}
Вхідні дані #1
4 6 1 1 1 2 1 1 3 1 1 4 1 2 3 2 2 4 4 3 4 3
Вихідні дані #1
6
Вхідні дані #2
4 3 2 1 2 1 2 1 2 3 7 3 4 5
Вихідні дані #2
impossible