提示: 欢迎访问OurACM平台。
Problem 1703 Terrorist Attack

Accept: 81    Submit: 366
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Berland is consisted of N cities, some of which are connected by M roads. There is at least one path from any city to another. At present, the country is under terrorist attack. According to reliable information, the terrorists will only attack one road. If this road is attacked, it will be impassability. Now the king asks you whether there is at least one path between any two cities after some road was attacked. If so, what will be the total length of roads of the minimum spanning tree.

Input

For each test case, the first line are two integers N (1 ≤ N ≤ 10,000) and M (1 ≤ M ≤ 100,000), indicating the number of cities and the number of roads. The ith line of the following M lines contains three numbers A,B and L ( 1 ≤ A ≤ N , 1 ≤ B ≤ N, 1 ≤ L ≤ 10000) ,indicating that the ith road is between city A and B and its length is L.

The next line contains a single integer Q ( 1 ≤ Q ≤ 10,000), which is the number of queries. Each of the following Q lines contains a number X , indicating that the ith road will be attacked.

Output

For each query, print a line containing the total length of the minimum spanning tree if at least one path exists between every pair of city, or “Not connected” otherwise.

Sample Input

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

Sample Output

15 13 9 Not connected

Hint

huge input, “scanf” is recommend in order to avoid Time Limit Exceed.

Source

FOJ-2009年4月月赛 Coral

Submit  Back  Status  Discuss