eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Стаціонарна телефона мережа

Стаціонарна телефона мережа

Мер міста 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 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #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
Джерело 2014 ACM North America - Rocky Mountain, Problem F