Problem E
Alien Clown Magnets

Alien Clown Magnets (ACM), Inc., the largest manufacturer of magnets that look like alien clowns in the world, has been financially struggling as their energy costs have sky-rocketed due to the insatiable demand for alien clown magnets. As CEO, you have determined that the best way to reduce these costs significantly is to switch to solar power in all of the manufacturing plants. While it would be nice to install solar panels at every plant, it may be cheaper to connect some plants to other plants with existing solar panels. Your goal is to get the cheapest cost plan to implement so that every plant has access to solar power. As you are working on a tight budget, there is a limited number of solar panels that you can use. A plant can be considered to have access to solar power if either it has solar panels, or if a plant can connect to a plant with solar panels through a connection of wires (i.e a plant can connect directly to a plant with solar panels, or it can connect to another plant that may access a plant with solar panels). You can assume that each plant with solar panels generates enough electricity to power all connected plants, and the electricity can flow both ways through the connections. Note: there can exist multiple direct connections between two plants of different costs, as installing connections through different terrains have different costs.

Input

The first line consists of the number of test cases, $N$, where $N \leq 5$. Each test case begins with four integers $P$, $L$, $S$, $R$, where $P$ is the number of manufacturing plants ($0<P \leq 10,000$) numbered 1 to $P$, $L$ is the number of possible connections that can created between plants ($0 \leq L \leq 50,000$), $S$ is the cost of installing solar panels at a plant ($0<S \leq 10,000$), and $R$ is the maximum number of solar panels available ($0 < R \leq 50,000$). The next $L$ lines consist of the three integers $A$, $B$, $C$, where $A$ and $B$ are manufacturing plants ($0<A,B \leq P$), and $C$ is the cost of building a connection between $A$ and $B$ ($0<C \leq 10,000$).

Output

For each test case, output the minimum cost of installing solar panels at plants, and creating connections between plants such that each plant has access to solar power.

1
5 4 100 3
0 1 50
2 3 120
0 3 40
1 2 100

390

1
7 5 100 10
0 2 90
1 3 120
0 4 100
5 6 40
4 7 30

560