eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

В городе Фловиль были проведены выборы T чиновников. Сам город можно представить в виде связного неориентированного графа, состоящего из N вершин и M рёбер. Каждое ребро графа задаётся тройкой чисел: u_iv_ilen_i (ребро между вершинами u_i и v_i) len_i - длина ребра.

Каждому чиновнику предоставляется жильё. Чиновнику с номером t предоставляется жильё в вершине графа с номером h_t. В городе имеется T свободных офисов для работы чиновников. Если чиновнику с номером t предоставлен офис в вершине графа с номером w_t, то ежедневно чиновнику необходимо ехать на автомобиле из вершины h_t в вершину w_t. Чиновник обязательно будет ехать по кратчайшему пути. Из всех возможных кратчайших путей он выбирает маршрут по следующему правилу: упорядочим номера вершин маршрута в обратном порядке (т.е. от места работы к дому) и выберем «лексикографически наименьший» путь.

Например, если существуют 2 кратчайших пути из вершины 0 в вершину 5: 0→1→2→4→5 и 0→3→5, то чиновник выберет путь 0→3→5. Т.к. в обратном порядке (от места работы к дому): 5→4→2→1→0 и 5→3→0. А «лексикографически наименьший» - это 5→3→0.

Все дороги (рёбра графа) лежащие вдоль маршрута чиновника всегда будут будут поддерживаться в хорошем состоянии.

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

Input data

В первой строке через пробел заданы три целых числа N, M и T.

N - количество вершин графа (N \le 100);

M - количество рёбер в графе (M \le 1000);

T - количество чиновников (T \le 8);

Далее идут M строк, описывающих рёбра графа. Каждое ребро задано в формате: u_iv_ilen_i, где len_i - длина ребра (0 \le u_i, v_i \le n), (len_i \le 100000).

Далее идёт строка из T целых чисел:

0 \le h_1, h_2, …, h_t, …, h_T \le n - номера вершин, в которых находятся дома чиновников;

Далее идёт строка из T целых чисел:

0 \le w_1, w_2, …, w_t, …, w_T \le n - номера вершин, в которых находятся офисы для будущей работы чиновников.

Output data

SUM - максимальная суммарная длина дорог, которые будут гарантированно отремонтированы.

0 \le w_res1, w_res2, …, w_rest, …, w_resT \le n - номера вершин, в которых находятся офисы для будущей работы чиновников, соответствующие максимальной суммарной длине гарантированно отремонтированных дорог SUM.

Examples

Input example #1
2 1 1
0 1 23153
0
1
Output example #1
23153
1
Input example #10
4 6 2
0 1 29108
1 2 9431
2 3 13527
1 3 11700
0 3 15800
0 2 32762
0 2
1 3
Output example #10
41027
1 3
Input example #11
4 6 2
0 2 28448
1 2 20356
2 3 20979
1 3 11573
0 3 5345
0 1 1920
1 2
0 3
Output example #11
27621
3 0
Input example #12
8 28 4
0 6 18908
1 2 10301
2 6 16463
3 7 17955
4 6 24411
5 7 20593
6 7 14513
4 5 8815
1 5 27654
2 5 20498
5 6 2903
0 2 5948
0 3 10273
1 6 27176
0 4 20959
0 7 27279
3 5 20876
0 1 10508
0 5 30777
4 7 9098
2 4 9328
2 3 15458
2 7 5043
3 4 12659
1 4 271
1 7 32408
3 6 17316
1 3 28695
3 4 6 7
0 1 2 5
Output example #12
58582
1 2 0 5
Author Биданец Александр, Олег Тихий