解为基环树森林
证明其具有拟阵的性质：
1、空集独立
2、基环树森林的子集仍然是基环树森林，满足遗传特性
3、对于基环树森林A，B，若|A|<|B| （边数），一定可以找到一条边e∈B，∉A，使A∪e仍然是基环树森林，满足扩充特性
扩充特性证明：
枚举A中的联通块
1、若A中这个联通块的边数<B中对应联通块的边数，显然存在一条满足要求的边
2、否则B中存在一条边连接了A的两个联通块。枚举B中这样的边，若这两个联通块至少有一个不是基环树，则该边满足要求。
否则，A中这两个联通块都是基环树，B中不是基环树，因此B中这个联通块的边数<A中这两个联通块的边数和。所以还存在其他的联通块之间的边满足要求
所以本题解法：
按边权从大到小排序，先构造出一颗最大权值基环树
然后按边权从大到小枚举之前没有用过的边u--v
首先明确不会存在原来联通块是树，加上这条边变成基环树的情况
因为之前已经构造了最大权值基环树
1、若u和v在同一个联通块，该联通块一定是基环树，那么新加的这条边可以替换环上的任意一条边，也可以替换u和v到环的路径上的一条边
2、若u和v不在同一个联通块，那么这两个联通块都是基环树，这条边可以替换两个环上的任意一条边，也可以替换u和v到环的路径上的一条边
无论哪种情况，都是用当前边去替换最大权值基环树上的边
遇上已经被替换过一次的边则停止替换，因为之前用的边的边权不会比现在的边的边权小
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; typedef long long LL; #define N 200001 struct node
{
int u,v,w;
int id;
bool use;
}e[N]; LL ans[N]; int fa[N],siz_p[N],siz_e[N];
int circle[N];//基环的环在哪儿 struct graph
{
int from,to,id,w;
int nxt;
}g[N<<];
int tot,front[N];
int pre[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} bool cmp(node p,node q)
{
return p.w>q.w;
} int find(int i) { return fa[i]==i ? i : fa[i]=find(fa[i]); } void unionn(int u,int v)
{
int fu=find(u),fv=find(v);
if(fu==fv)
{
circle[fu]=u;
siz_e[fu]++;
return;
}
fa[fu]=fv;
siz_e[fv]+=siz_e[fu]+;
siz_p[fv]+=siz_p[fu];
circle[fv]|=circle[fu];
} void add(int u,int v,int t)
{
g[++tot].from=u; g[tot].to=v; g[tot].id=e[t].id; g[tot].w=e[t].w; g[tot].nxt=front[u]; front[u]=tot;
g[++tot].from=v; g[tot].to=u; g[tot].id=e[t].id; g[tot].w=e[t].w; g[tot].nxt=front[v]; front[v]=tot;
} int dfs(int now,int last)
{
int tmp=,t;
for(int i=front[now];i;i=g[i].nxt)
{
t=g[i].to;
if(t==last) continue;
if(pre[t]==-) tmp=i;
if(pre[t]) continue;
pre[t]=i;
tmp|=dfs(t,now);
}
return tmp;
} void concat(int x,int w)
{
int now;
while()
{
now=pre[x];
if(ans[g[now].id]) break;
ans[g[now].id]=ans[]-g[now].w+w;
x=g[now].from;
}
} void out(LL x)
{
if(x>) out(x/);
putchar(x%+'');
} int main()
{
freopen("journey.in","r",stdin);
freopen("journey.out","w",stdout);
int n,m;
read(n); read(m);
for(int i=;i<=m;++i)
{
read(e[i].u); read(e[i].v); read(e[i].w);
e[i].id=i;
}
sort(e+,e+m+,cmp);
for(int i=;i<=n;++i)
{
fa[i]=i;
siz_p[i]=;
}
int fu,fv;
for(int i=;i<=m;++i)
{
fu=find(e[i].u);
fv=find(e[i].v);
if(siz_p[fu]==siz_e[fu] && siz_p[fv]==siz_e[fv]) continue;
ans[]+=e[i].w;
e[i].use=true;
unionn(e[i].u,e[i].v);
add(e[i].u,e[i].v,i); }
int u;
for(int i=;i<=n;++i)
{
u=find(i);
if(circle[u]) u=circle[u];
if(!pre[u])
{
pre[u]=-;
pre[u]=dfs(u,-);
}
}
for(int i=;i<=m;++i)
{
if(e[i].use) continue;
ans[e[i].id]=ans[];
concat(e[i].u,e[i].w);
concat(e[i].v,e[i].w);
}
for(int i=;i<=m;++i)
if(!ans[e[i].id]) ans[e[i].id]=ans[]-e[i].w;
for(int i=;i<=m;++i) out(ans[i]),putchar('\n');
}