"The world is full of ifs. The world we exist in is merely one of the results of a vast number of ifs, and the future is a world chaotically flowing due to an infinite number of ifs."

In one particular world line, you might be running a multinational corporation—doesn't that sound exciting? In that world, you are troubled by the design of your marketing network.

Your multinational corporation has established sales outlets in $n$ countries, numbered from $1$ to $n$. These $n$ countries are connected by $m$ bidirectional air routes. If we treat countries as nodes and air routes as edges, this can be abstracted as an undirected graph.

You have already established branch offices in $S$ of these countries. You intend to purchase VIP status for some air routes to accelerate your product transportation.

Regardless of what deviations occurred in this world line, the fact that you are an OIer remains unchanged, so you have strict requirements for your VIP air route purchase plan:

1. Starting from any country, it is impossible to return to the starting point by traveling only through VIP air routes without visiting any country more than once. That is, the purchased VIP air routes must form a spanning forest of the original graph.
2. Starting from any branch office, it must be possible to reach any other branch office by traveling only through VIP air routes.

Each air route has a weight representing the cost of purchasing VIP status for that route. As a sharp-minded person, you must have immediately identified the minimum total cost to achieve your goal. However, that is not sufficiently willful or extravagant, and it would inevitably affect the future development of the company. Therefore, as a clever person, you decide to find the $k$ smallest total costs for VIP air route purchase plans.

Two VIP air route purchase plans are considered different if and only if there exists at least one air route that is purchased as a VIP route in one plan but not in the other.

"An if is just an if. Even if there exists a parallel world with a good if, humans cannot simply cross world lines to get there."

But it is still pleasant to daydream a little, so please solve this problem.

Brief Problem Statement: Find the $k$ smallest spanning forests such that the given $S$ nodes are pairwise reachable within the forest.

Input

The first line contains four positive integers $n, m, S, k$.

The second line contains $S$ positive integers, representing the countries where branch offices are located. It is guaranteed that the given country numbers are distinct.

The next $m$ lines each contain three positive integers $u_i, v_i, c_i$, representing an air route between countries $u_i$ and $v_i$ with a cost of $c_i$. It is guaranteed that $1 \leq u_i, v_i \leq n$ and $u_i \neq v_i$.

Output

Output $k$ lines, each containing a single positive integer. The $i$-th line should contain the total cost of the $i$-th smallest VIP air route purchase plan.

Examples

Input 1

6 9 3 6
3 1 5
1 2 1
1 3 2
3 2 2
2 4 5
3 4 5
3 5 2
3 6 2
6 4 4
5 6 1

Output 1

4
5
5
5
5
6

Constraints

Except for the sample provided in the problem, the air routes and the countries with branch offices are generated uniformly at random for fixed $n, m, S$. For all air routes, $c_i$ is an integer chosen uniformly at random from $1$ to $100$.

It is guaranteed that at least $k$ different VIP air route purchase plans exist.