K-th Minimum VIP Flight Purchase Plan

In this problem, you are given an undirected graph representing a network of n countries (nodes) connected by m bidirectional flight routes (edges). Your company has established branches in a subset of these countries, given by the set S. You want to purchase some routes as VIP in order to speed up the transportation of your products. However, your purchasing plan must satisfy the following two strict conditions:

1. The VIP routes form a spanning forest of the original graph. In other words, if you start at any country, it is impossible to travel using only VIP routes and return to the starting point without repeating any country (i.e. the VIP routes are acyclic and maximal).
2. For any two branch countries (those in S), there is a path using only VIP routes between them.

Two VIP purchase plans are considered different if and only if there is at least one route that is chosen as VIP in one plan and not in the other. Each route has an associated cost of buying the VIP upgrade. You have likely noticed that there is a plan with minimum total cost; however, you are interested in exploring other options as well. Your task is to list the total costs of the first k smallest valid VIP purchase plans, where the total cost is the sum of the costs of the selected VIP routes. If there are fewer than k valid plans, output -1 for each missing plan.

Important Note (in LaTeX): A spanning forest F of the graph G=(V,E) is a subset of edges such that for every connected component C (with |C| vertices), F restricted to C forms a spanning tree. In our problem, if V is partitioned into components by the original graph, then for each component C we must have exactly \( |C|-1 \) edges chosen and the branch nodes in S (which are guaranteed to lie in one component) must be in the same tree.

Input Format: The input begins with two integers n and m, representing the number of countries and the number of routes respectively. This is followed by m lines, each containing three integers u, v, and w which denote a bidirectional route connecting countries u and v with a cost of w (\( w>0 \)). Then an integer t is given, representing the number of branch countries, followed by a line of t distinct integers listing the branch country indices. The final line contains an integer k, indicating that you need to output the total cost of the first k smallest valid plans.

Output Format: Output exactly k lines. The i-th line should contain a single integer: the total cost of the i-th smallest valid VIP flight purchase plan. If there are fewer than k valid solutions, output -1 on the missing lines.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10), where n is the number of countries and m is the number of routes.

The next m lines each contain three space‐separated integers u, v and w, denoting a bidirectional flight route connecting country u and country v with cost w (1 ≤ u, v ≤ n, w > 0).

The following line contains an integer t, the number of branch countries.

The next line contains t distinct space‐separated integers, representing the branch country indices.

The last line contains an integer k, representing the number of smallest valid plans to output.

outputFormat

Output k lines. The i-th line should contain the total cost (an integer) of the i-th smallest valid VIP purchase plan. If there are fewer than k valid solutions, output -1 for each remaining line.

sample

3 3
1 2 1
2 3 2
1 3 3
2
1 3
3

3
4
5