Officials and Roads

In the city of Floville, elections have been held for $T$ officials. The city is represented as a connected undirected graph with $N$ vertices and $M$ edges. Each edge in the graph is described by a triplet of numbers: $u_i$, $v_i$, and $le{n}_i$, indicating an edge between vertices $u_i$ and $v_i$ with a length of $le{n}_i$.

Each official is provided with housing. Official number $t$ resides at vertex $h_t$ on the graph. There are $T$ available offices in the city for the officials to work from. If official number $t$ is assigned to an office at vertex $w_t$, they will commute daily from vertex $h_t$ to vertex $w_t$, always taking the shortest path. Among all possible shortest paths, they choose based on the following rule: reverse the order of the vertices in the path (i.e., from the workplace to home) and select the "lexicographically smallest" path.

For instance, if there are two shortest paths from vertex 0 to vertex 5: 0→1→2→4→5 and 0→3→5, the official will choose the path 0→3→5. This is because, in reverse order (from workplace to home), the paths are 5→4→2→1→0 and 5→3→0. The "lexicographically smallest" is 5→3→0.

All roads (graph edges) along the official's route will be maintained in good condition.

Each official must select one office from the list such that the total length of roads maintained in good condition is maximized.

Input

The first line contains three integers $N$, $M$, and $T$:

- $N$: the number of vertices in the graph ($N\le 100$); - $M$: the number of edges in the graph ($M\le 1000$); - $T$: the number of officials ($T\le 8$).

The next $M$ lines describe the edges of the graph. Each edge is given in the format: $u_i$ $v_i$ $le{n}_i$, where $le{n}_i$ is the length of the edge ($0\le u_i,v_i\le n$), ($le{n}_i\le 100000$).

The following line contains $T$ integers:

- $0\le h_1,h_2,\dots ,h_T\le n$: the vertex numbers where the officials' homes are located.

The next line contains $T$ integers:

- $0\le w_1,w_2,\dots ,w_T\le n$: the vertex numbers where the offices for the officials' future work are located.

Output

Output $S$, the maximum total length of roads that will be guaranteed to be repaired.

Also, output $0\le w_{res,1},w_{res,2},\dots ,w_{res,T}\le n$: the vertex numbers where the offices for the officials' future work are located, corresponding to the maximum total length of guaranteed repaired roads $S$.

Examples