rt

思路：kruskal倒着打

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edge{
	int from,to,len,num;
}axium[6005];//存边的
int ans[6005];//存那些个结果
int fa[6005];//存爹
bool used[6005];//存要不要过
bool canuse[6005];//存能不能用
int find(int a){
	if(fa[a]==a)return a;
	return fa[a]=find(fa[a]);
}
void bind(int a,int b){
	fa[find(a)]=find(b);
}
bool cmp(edge a,edge b){
	return a.len<b.len; 
}
int main(){
	cin>>n>>m;
	bool sto=0;
	for(int i=0;i<m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		axium[i].from=x;
		axium[i].to=y;
		axium[i].len=z;
		axium[i].num=i;
	}
	memset(used,0,sizeof(used));memset(canuse,1,sizeof(used));
	sort(axium,axium+m,cmp);
	for(int i=m-1;i>=0;i--){
		if(sto){//是不是都完不成了
			ans[i]=-1;
			continue;
		}
		for(int j=0;j<m;j++){
			fa[i]=i;
		}
		bool orz=1;
		for(int j=0;j<m;j++){
			if(axium[j].num==i){
				canuse[j]=0;
				if(used[j]==0)ans[i]=ans[i+1],orz=0;
				break; 
			}
		}
		if(!orz)continue;
		int k=0;
		int ansqwq=0;
		for(int j=0;j<m;j++){
			if(canuse[j]&&find(axium[j].from)!=find(axium[j].to)){
				bind(axium[j].from,axium[j].to);
				ansqwq+=axium[j].num;
				k++;
				
			}
			
			if(k==n-1)break;
		}
		
		if(k<n-1){
			sto=1;
			ans[i]=-1;
			continue;
		}
		ans[i]=ansqwq;	}
		for(int i=0;i<m;i++){
			cout<<ans[i]<<endl;
		}
	return 0;
}

好 一 平 orzorz