Mst

时间限制:20s      空间限制:256MB

题目描述

给出一个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%的数据如题目。<="" pre="">

提示

 更新数据---2015.6.9


题目来源

没有写明来源

Menuappsclose