题解：P9926 [NFLSPC #6] 所以 k 小生成树怎么做？
k 小值问题当然要考虑经典做法：
- 建出一颗外向树，满足每个状态都由不大于它的状态转移而来。
- 在这颗生成树上维护一个堆，每次取出最小的状态，把它指向的所有状态加入堆中。
初始状态当然是最小生成树。
我们希望每个状态的出边数量不多，也就是不能每次直接枚举一条边替换。
那么我们选择直接先找到最小的替换边，即选出树边
由于可能不选这条边，我们可以先选到这个替换边，然后再走到这个点的时候反悔去选另一条次小的替换边。
这里由于复杂度的原因，我们这里最小次小指得是对于每条树边，也就是对于每一条树边先找到覆盖它的最小权非树边然后排序得到的，而反悔时就在之后要求必须选这条树边。
而寻找覆盖树边的最小权非树边可以扫描线后通过并查集维护。
不过我们还要保证每个状态的得到路径存在且唯一，我们考虑当前状态和目标状态，每次找到当前状态的最小转移边，如果目标状态也有这条边则跳过，如果没有就可以加入这条边并让这条边不能被反悔，由于总权值增大有限步会停止。
最后拿个堆维护就好了，时间复杂度
#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;
}