题目描述

给定一张无向带权无自环无重边的连通图，求前 $k$ 小生成树的权值。

• 生成树的权值为其所有边权之和。
• 两棵生成树不同，当且仅当存在一条边在一棵生成树上，但不在另一棵生成树上。
• 若第 $i$ 小生成树不存在，则输出 $-1$。

输入格式

第一行三个整数 $n, m, k$。

接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$，分别表示无向边的两端及其权值。

输出格式

输出 $k$ 行，第 $i$ 行一个整数表示第 $i$ 小生成树的权值。

输入输出样例 #1

输入 #1

4 6 17
1 2 4
1 3 7
1 4 6
2 3 8
2 4 5
3 4 7

输出 #1

16
16
17
17
17
18
18
18
18
19
19
19
20
21
21
22
-1

说明/提示

对于所有数据，$1\leq n \leq 5\times 10 ^ 4$，$n - 1\leq m\leq 10 ^ 5$，$1\leq k\leq 10 ^ 5$，$1\leq mk\leq 10 ^ 7$，$1\leq u_i, v_i\leq n$，$1\leq w_i\leq 10 ^ 9$。保证图连通，无自环，无重边。

• 子任务 1（$10$ 分）：$m ^ 2k\leq 10 ^ 6$。
• 子任务 2（$20$ 分）：保证每条边至多属于一个简单环。
• 子任务 3（$20$ 分）：$mk\leq 10 ^ 6$。
• 子任务 4（$50$ 分）：无特殊限制。

#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<queue>
#include<bitset>
#include<cstdio>
#include<vector>
#include<random>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#define I ll
#define her1 20081214
#define IV void
#define cht 1000000007
#define ld long double
#define Aestas16 392699
#define ull unsigned long long
#define cp(x,y)memcpy(x,y,sizeof y)
#define mem(x,val)memset(x,val,sizeof x)
#define D(i,j,n)for(register int i=j;i>=n;i--)
#define E(i,now)for(register int i=first[now];i;i=e[i].nxt)
#define F(i,j,n)for(register int i=j;i<=n;i++)
#define DL(i,j,n)for(register i64 i=j;i>=n;i--)
#define EL(i,now)for(register i64 i=first[now];i;i=e[i].nxt)
#define FL(i,j,n)for(register i64 i=j;i<=n;i++)
//#define D(i,j,n)for(int i=j;i>=n;i--)
//#define E(i,now)for(int i=first[now];i;i=e[i].nxt)
//#define F(i,j,n)for(int i=j;i<=n;i++)
//#define DL(i,j,n)for(register ll i=j;i>=n;i--)
//#define EL(i,now)for(register ll i=first[now];i;i=e[i].nxt)
//#define FL(i,j,n)for(register ll i=j;i<=n;i++)
ll read(){
	ll ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')ans=ans*10+c-'0',c=getchar();
	return ans*f;
}
#undef ll
#include "assert.h"
mt19937_64 rnd(her1);
#include "functional"
using i64 = long long;
const int maxn = 1e5+5;
const i64 oo = 1e18;

i64 n,m,k,tot;
struct edge{i64 u,v,w;}a[maxn];
bool operator<(const edge&A,const edge&B){
	return A.w<B.w;
}
struct dsu{
	i64 fa[maxn];
	IV init(){F(i,0,n-1)fa[i]=i;}
	i64 find(i64 x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	IV merge(i64 x,i64 y){x=find(x);y=find(y);fa[y]=x;}
}tr;
struct dat{
	i64 del,add,from,val;
	bool operator<(const dat&z)const{
		return val>z.val;
	}
};
struct node{
	i64 dft,val;
	vector<vector<i64> >e;
	vector<i64>st,fa,dfn,siz,lab;
	IV dfs(i64 x,i64 F){
		fa[x]=F;dfn[x]=++dft;siz[x]=1;
		for(i64 i:e[x])if(i!=F)dfs(i,x),siz[x]+=siz[i];
	}
	bool anc(i64 x,i64 y){return dfn[x]<=dfn[y]&&dfn[x]+siz[x]>dfn[y];}
	IV init(){
		fa.resize(n);dfn.resize(n);
		siz.resize(n);lab.resize(n);

		dfs(0,0);
		F(i,0,m-1)if(st[i]&1){
			i64 u=::a[i].u,v=::a[i].v;
			if(anc(v,u))swap(u,v);lab[v]=i;
		}
	}
	dat suc(){
		tr.init();
		i64 del=-1,add=-1,dlt=oo;
		F(i,0,m-1){
			if(st[i])continue;
			i64 u=a[i].u,v=a[i].v;
			F(kkk,1,2){
				while(1){
					u=tr.find(u);
					if(anc(u,v))break;tr.merge(fa[u],u);
					i64 x=lab[u],dltx=a[i].w-a[x].w;
					// cout<<i<<' '<<x<<endl;
					if(st[x]==3)dltx=oo;
					if(dltx<dlt)dlt=dltx,del=x,add=i;
				}
				u=a[i].u,swap(u,v);
			}
		}
		// cout<<dlt<<endl;
		return{del,add,-1,dlt};
	}
}mst;
vector<node>st;
IV init(){
	st.resize(k);mst.st.resize(m);
	mst.e.resize(n,vector<i64>());tr.init();
	F(i,0,m-1){
		i64 u=tr.find(a[i].u),v=tr.find(a[i].v);
		if(u!=v){
			mst.st[i]=1;mst.val+=a[i].w;
			mst.e[a[i].u].push_back(a[i].v);
			mst.e[a[i].v].push_back(a[i].u);
			tr.merge(u,v);
		}
	}
}
IV kmst(){
	priority_queue<dat>q;
	q.push({-1,-1,-1,mst.val});
	i64 id=0;
	while(k&&!q.empty()){
		dat t=q.top();q.pop();
		printf("%lld\n",t.val);k--;
		// puts("?");
		node&z=st[id];
		if(t.from==-1)z=mst;
		else{
			z=st[t.from];z.dft=0;z.val=t.val;
			i64 u=a[t.del].u,v=a[t.del].v;
			z.e[u].erase(find(z.e[u].begin(),z.e[u].end(),v));
			z.e[v].erase(find(z.e[v].begin(),z.e[v].end(),u));
			u=a[t.add].u,v=a[t.add].v;
			z.e[u].push_back(v);
			z.e[v].push_back(u);
			z.st[t.del]=0,z.st[t.add]=3;
			st[t.from].st[t.add]=2;
			dat res=st[t.from].suc();
			res.from=t.from;
			// cout<<res.val<<endl;
			res.val+=st[t.from].val;
			if(res.add!=-1)q.push(res);
		}
		z.init();
		dat res=z.suc();
		res.from=id,res.val+=t.val;
		if(res.add!=-1)q.push(res);
		id++;
	}
	while(k--)puts("-1");
}
int main(){
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	n=read();m=read();k=read();
	F(i,0,m-1){
		a[i].u=read();a[i].v=read();a[i].w=read();
		a[i].u--;a[i].v--;
	}
	sort(a,a+m);
	init();kmst();
	return 0;
}