这题目很water
只要按照题意模拟就行了，数据似乎没有重边，那么对于加入每一条边的时候，如果两端点没联通，那么连上，反之
先连上，形成一个环，去点环上最大的边
数据范围不大对
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int head[3000001];
int x,y,z;
int n,m;
int p;
int vis[6000001];
int re[6000001];
struct b{
int f;
int to;
int ne;
int v;
}ed[6000001];
void add(int f,int to,int v){
p++;
ed[p].to=to;
ed[p].ne=head[f];
ed[p].f=f;
ed[p].v=v; ;
head[f]=p;
p++;
re[p-1]=p;
re[p]=p-1;
ed[p].to=f;
ed[p].ne=head[to];
ed[p].f=to;
ed[p].v=v;
head[to]=p;
return ;
}
int fa[400001];
int find(int x){
return x==fa[x]? x:fa[x]=find(fa[x]);
}
int cnt;
int f;
int ans;
int res;
void dfs(int now,int aim,int maxx,int la){
if(f)
return ;
if(now==aim){
f=1;
res=maxx;
return ;
}
for(int i=head[now];i;i=ed[i].ne){
if(!vis[i]&&!vis[re[i]]&&ed[i].to!=la){
//dfs(ed[i].to,aim,max(maxx,ed[i].v),now);
if(ed[i].v>ed[maxx].v)
dfs(ed[i].to,aim,i,now);
else
dfs(ed[i].to,aim,maxx,now);
}
}
}
void work(int x,int y,int z){
if(find(x)!=find(y)){
fa[fa[x]]=fa[y];
add(x,y,z);
cnt++;
ans+=z;
}else{
f=0;
dfs(x,y,0,0);
if(ed[res].v>=z){
add(x,y,z);
ans+=z-ed[res].v;
vis[res]=vis[re[res]]=1;
}
}
if(cnt!=n-1){
cout<<-1<<endl;
return ;
}else{
cout<<ans<<endl;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
fa[i]=i;
for(int i=1;i<=m;++i){
scanf("%d%d%d",&x,&y,&z);
work(x,y,z);
}
return 0;
}