#2238. Mst

题目描述

给出一个 N 个点 M 条边的无向带权图，以及 Q 个询问，每次询问在图中删掉一条边后图的最小生成树。(各询问间独立，每次询问不对之后的询问产生影响，即被删掉的边在下一条询问中依然存在)

输入格式

第一行两个正整数N,M(N<=50000,M<=100000)表示原图的顶点数和边数。

下面M行，每行三个整数X,Y,W描述了图的一条边(X,Y)，其边权为W（W<=10000）。保证两点之间至多只有一条边。

接着一行一个正整数Q，表示询问数。(1<=Q<=100000)

下面Q行，每行一个询问，询问中包含一个正整数T，表示把编号为T的边删掉(边从1到M按输入顺序编号)。

输出格式

Q行，对于每个询问输出对应最小生成树的边权和的值，如果图不连通则输出"Not connected"

样例

样例输入

4 4  

1 2 3   

1 3 5   

2 3 9   

2 4 1   

4   

1   

2   

3   

4  

样例输出

15   

13   

9   

Not connected  

   

样例解释:  

无  

   

数据规模：  

10%的数据N,M,Q<=100。  

另外30%的数据，N<=1000  

100%的数据如题目。

数据范围与提示

更新数据---2015.6.9