В городе Фловиль были проведены выборы $T$ чиновников. Сам город можно представить в виде связного неориентированного графа, состоящего из $N$ вершин и $M$ рёбер. Каждое ребро графа задаётся тройкой чисел: $u_i$ $v_i$ $len_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. Все дороги (рёбра графа) лежащие вдоль маршрута чиновника всегда будут будут поддерживаться в хорошем состоянии. Каждому чиновнику необходимо выбрать только один офис из имеющихся в списке так, чтобы суммарная длина дорог, находящихся в хорошем состоянии, была максимальной. \InputFile В первой строке через пробел заданы три целых числа $N$, $M$ и $T$. $N$ - количество вершин графа ($N \le 100$); $M$ - количество рёбер в графе ($M \le 1000$); $T$ - количество чиновников ($T \le 8$); Далее идут $M$ строк, описывающих рёбра графа. Каждое ребро задано в формате: $u_i$ $v_i$ $len_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$ - номера вершин, в которых находятся офисы для будущей работы чиновников. \OutputFile $SUM$ - максимальная суммарная длина дорог, которые будут гарантированно отремонтированы. $0 \le w_res1, w_res2, …, w_rest, …, w_resT \le n$ - номера вершин, в которых находятся офисы для будущей работы чиновников, соответствующие максимальной суммарной длине гарантированно отремонтированных дорог $SUM$.