Problem I
World Of 3

The Monster Hunter World games have arrived. In your quest to become the best hunter in the land, you have to hunt all the monsters in the land and present them to the king, who will give you a handsome reward for your endeavours. There are various quests to complete and monsters to hunt in order to satisfy the king, along with fierce competition from other hunters. Hence, time is of the essence.

The world is vast and barren, with many monsters present. More formally, the world can be modelled as having $N$ cities and $E$ roads. There are $K$ cities where quests must be completed. Completing a quest takes a negligible amount of time. It is guaranteed that there exists a path between any $2$ cities.

Hunters in this world are equipped with Mana, which enables them to use spells efficiently.

Being an intelligent hunter, you know that farming all quests is going to be very time consuming and challenging. Therefore, you have sought the help of the witch, who will grant you an insurmountable power that many hunters will envy.

The way this spell works is as follows:

1. From the $N$ cities, choose a subset for which you want to complete your quests (if there are any). You may choose up to $A_{max}$ cities.

2. For each city in the subset you choose, the quest in that city will be completed.

3. You may then choose a single city in this subset to teleport to. Note that the previous $2$ steps all happen instantaneously.

4. Your mana will be reset to $0$.

You may only use this spell if you have at least $T$ mana. You initially start with $0$ mana. You recharge $1$ unit of mana per time, while travelling between cities or waiting at any city.

In order to not raise suspicion from other Hunters, you can only use the spell at $L$ specific cities. All $L$ of these cities have attached quests. You are currently at city $1$. Calculate the minimum possible time taken to complete all quests from all $K$ cities and return to city $1$, in order to become the greatest Monster Hunter in the land!

Input

The first line contains $6$ integers, $1 \le N \le 100\, 000$, $1 \le E \le 200\, 000$, $1 \leq K \leq min(14, N)$, $1 \leq T \leq 10^{9}$, $0 \leq L \leq K$, $1 \leq A_{max} \leq K$.

The next $E$ lines contain the roads, each on one line. Each road is given in the form $u\, v\, w$ where $u,v$ are the $2$ endpoints of a road ($1 \leq u,v \leq N$) and $w$ is the time taken to travel through a road ($1 \le w \le 10^{9}$). The roads can be traversed in both directions.

The next $K$ lines contain the cities with quests, where $2 \leq K_{i} \leq N$.

The next $L$ lines contain the cities from which you can use the spell from, where $2 \leq L_{i} \leq N$. It is guaranteed that there is a quest in each of these cities.

Output

Print the answer on $1$ line, the minimum time required.

Explanation of Sample Input 3

1. You can travel from city $1$ to cities $3$, $4$, $5$ in that order, taking a total of $33$ units of time. During this, complete the quests at cities $3$, $4$, and $5$.

2. From city $5$, go back to city $4$, taking $11$ units of time. Note that at this point, $44$ units of time have elapsed, and we have accumulated $44$ Mana.

3. Use the spell at city $4$, selecting cities $\{ 1, 2\} $ to complete quests in. Note that we may select $1$, even if we have no quest there. After completing quests, teleport to city $1$.

4. You now have $0$ Mana, and have returned to city $1$.

This takes up $44$ units of time. It can be shown that it is impossible to complete all quests in less time. Therefore, the answer is $44$.

5 8 2 8 1 2
1 2 51
1 3 101
1 4 91
3 2 11
3 4 71
3 5 91
4 2 41
4 5 51
3 4
4

91

5 9 3 6 2 3
1 2 101
2 3 21
2 4 91
2 5 1
3 1 41
3 4 41
3 5 61
4 5 71
5 1 41
5 4 2
5 4

41

5 8 4 1 1 2
1 2 101
1 3 11
1 4 51
1 5 61
2 3 41
3 4 11
4 2 21
4 5 11
5 2 4 3
4

44