记录编号	429684	评测结果	AAAAA
题目名称	公路建设	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.645 s
提交时间	2017-07-28 00:06:28	内存使用	0.34 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f; 
}
const int maxn=510;
const int maxm=2010;
int n,m;
struct edge {int u,v,w;}e[maxm];
inline bool cmp(edge a,edge b){return a.w<b.w;}
int tot;
int fa[maxn];
inline int find (int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline int kruskal(){
	int ans=0,cnt=0,f=0;
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(e+1,e+tot+1,cmp);
	for(int i=1;i<=tot;i++){
		int u=find(e[i].u),v=find(e[i].v);
		if(u!=v)fa[u]=v,ans+=e[i].w,cnt++;
		if(cnt==n-1){f=1;break;}
	}
	if(f==1)return ans;
	else return 0;
}
int main(){
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=m;i++){
		e[++tot].u=read(),e[tot].v=read(),e[tot].w=read();
		double cao=kruskal()*0.5;
		if(cao==0){puts("0");}
		else printf("%.1lf\n",cao);
	}
	return 0;
}