Чиновники і дороги

У місті Фловіль відбулися вибори $T$ чиновників. Місто можна уявити як зв'язний неорієнтований граф, що складається з $N$ вершин і $M$ ребер. Кожне ребро графа описується трійкою чисел: $u_i$, $v_i$, $le{n}_i$, де $u_i$ і $v_i$ — вершини, які з'єднує ребро, а $le{n}_i$ — його довжина.

Кожному чиновнику надається житло. Чиновнику з номером $t$ виділяється житло у вершині графа з номером $h_t$. У місті є $T$ офісів, де чиновники можуть працювати. Якщо чиновнику з номером $t$ виділено офіс у вершині графа з номером $w_t$, то він щодня їздитиме на автомобілі з вершини $h_t$ до вершини $w_t$. Чиновник завжди обирає найкоротший шлях. Якщо існує кілька найкоротших шляхів, він обирає той, що є «лексикографічно найменшим» при упорядкуванні вершин маршруту у зворотному порядку (від офісу до дому).

Наприклад, якщо є два найкоротші шляхи з вершини 0 до вершини 5: 0→1→2→4→5 і 0→3→5, то чиновник обере шлях 0→3→5. У зворотному порядку ці шляхи виглядають як 5→4→2→1→0 і 5→3→0. Лексикографічно найменший — це 5→3→0.

Усі дороги (ребра графа), що входять до маршруту чиновника, завжди будуть підтримуватися в хорошому стані.

Кожному чиновнику потрібно вибрати лише один офіс з наявних, щоб сумарна довжина доріг, які будуть у хорошому стані, була максимальною.

Вхідні дані

У першому рядку через пробіл задано три цілі числа $N$, $M$ та $T$.

$N$ — кількість вершин графа ($N\le 100$);

$M$ — кількість ребер у графі ($M\le 1000$);

$T$ — кількість чиновників ($T\le 8$);

Далі йдуть $M$ рядків, що описують ребра графа. Кожне ребро задано у форматі: $u_i$ $v_i$ $le{n}_i$, де $le{n}_i$ — довжина ребра ($0\le u_i,v_i\le n$), ($le{n}_i\le 100000$).

Далі йде рядок з $T$ цілих чисел:

$0\le h_1,h_2,\dots ,h_t,\dots ,h_T\le n$ — номери вершин, у яких знаходяться будинки чиновників;

Далі йде рядок з $T$ цілих чисел:

$0\le w_1,w_2,\dots ,w_t,\dots ,w_T\le n$ — номери вершин, у яких знаходяться офіси для майбутньої роботи чиновників.

Вихідні дані

$S$ — максимальна сумарна довжина доріг, які будуть гарантовано відремонтовані.

$0\le w_{res,1},w_{res,2},\dots ,w_{res,t},\dots ,w_{res,T}\le n$ — номери вершин, у яких знаходяться офіси для майбутньої роботи чиновників, що відповідають максимальній сумарній довжині гарантовано відремонтованих доріг $S$.

Приклади