403785: GYM101300 B Orders

Beetlejumpers have long been dreaming about having access to the numerous natural resources of the planet Stavromula Gamma. The local inhabitants do not even want to think about moving to less fertile territories. The military conflict seems to be inevitable, and supposing that the rumors are true, it will arise soon. The latest orders of the General Beattle, probably concerning the details of the attack, are of such a great importance that instead of being broadcast by a radio, they are delivered to the commanders personally.

The envelopes are marked with the sign ,,CONFIDENTIAL. Personal service", therefore their delivery may be carried out only by one of the three drivers accredited by the army. The army is in possession of super-fast vehicles – beetcars which were made available to the drivers. Due to the planned attack, such resources as fuel are priceless and must be used as efficiently as possible.

On the planet Stavromula Gamma, there are N cities marked with numbers from 1 to N and M two-way roads located between some of the cities. The network of the roads is so highly developed that for each city there is a certain set of the roads which allows for transportation to every other city.

The orders to the commanders of each of K units which are stationed on the planet Stavromula Gamma must be delivered with the use of three fast beetcars.

The drivers of the beetcars must deliver all envelopes and come back to the headquarters driving the shortest possible distance altogether (minimum distance in total). Moreover the habits present in the beetle army (always unconditionally observed by the army) require that the commanders become familiar with the wording of the orders in an appropriate order – the higher is their military rank, the sooner they should receive it.

The first line of the input includes two numbers: N and M, denoting the number of the cities and the number of the roads on the planet respectively. Each i-th line of the subsequent M lines consists of three numbers: a_i, b_i, d_i denoting that between the cities a_i and b_i there is a road measuring d_i. The next line consists of one number T which constitutes the number of test cases.

The following lines include the descriptions of these test cases. Each of them is composed of two lines. The first of the lines includes two integer numbers: H and K which stand for the identifier of the city in which the headquarters is located and the number of the units for which the orders should be delivered respectively. The second line of the description of the test case is composed of K numbers within the range from 1 to N. These are the identifiers of the cities where the units are stationed. They are listed exactly in the order according to which the orders are to be delivered.

1 ≤ N ≤ 10⁴

1 ≤ M ≤ 10⁶

1 ≤ a_i, b_i ≤ N

1 ≤ d_i ≤ 10⁶

1 ≤ T ≤ 10

1 ≤ H ≤ N

1 ≤ K ≤ 1000

For each test case, one integer number should be given in a separate line. Each value denotes the minimum distance that all three beetcars must go in total to deliver all orders from the headquarters and to go back to the headquarters. The values should be given in the same order as provided in the input data.

7 10
1 7 24
7 6 26
3 1 4
1 4 2
3 4 100
2 1 4
2 3 5
1 5 10
4 5 6
2 3 8
2
1 7
4 5 3 6 4 4 2
2 3
1 2 3

129
13

• All beetcars begin their trip from the city 1. The first beetcar goes to the city 4 and directly to the city 5, subsequently the second beetcar delivers the orders to the unit from the city 3 and the third one goes to 6 and returns to 1. At last, the first one goes from 5 to 1 through 4 and the second one from 3 to 1 through 2.

  1:

  2:

  3:

  1:

  2:

• At the beginning, all vehicles are located in the city 2. One of the beetcars goes subsequently through the city 1 and 3, in the meantime the second one delivers orders to the unit stationed in the city 2.

  1:

  2: 2

  1: