前言：
如果我自己写的话，或许能想出来正解，但是多半会因为整不出正确性而弃掉。
解析：
这题算是对Kruskal的熟练运用吧。
要求一颗生成树。也就是说，最后的边数是确定的。
首先我们容易想到一个策略：
先跑Kruskal，优先选k条石子路，剩下的选水泥路。
但是这样做显然是错误的。
因为，当随便选了k条石子路后，可能出现：
发现无论怎么选(n-1-k)条水泥路，也无法使图连通。如果这时选一条石子路，就可以保证连通性。
但是，发现这时已经选满了k条石子路，就没法再选石子路了。
我们可以通过设计一个策略来使这种情况不发生。
首先，我们可以优先用水泥路跑Kruskal，这时如果有一条石子路，如果不加上它，就无法保证连通性，那就将其打上标记，意思是这条石子路一定会出现在最后的答案里面。
第二遍Kruskal，先将上次打过标记的石子路加入并查集。然后，将石子路补成k条。
第三遍，补上水泥路。
这个策略为什么是正确的呢？
首先，可以发现，（设第一遍Kruskal找出了cnt条石子路）
执行第一遍Kruskal后，假如存在生成树，那么我们必然可以通过cnt条石子路+一些水泥路的方式来找到一颗生成树。
那么，此时我们再选一些石子路，相当于把一些水泥路换成了石子路。假如原来是有方案的，那么后面一定是有方案的。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxm=100000+10,maxn=20000+10;
#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
#define read() ({ register int x = 0, f = 1; register char c = gc(); while(c < '0' || c > '9') { if (c == '-') f = -1; c = gc();} while(c >= '0' && c <= '9') x = x * 10 + (c & 15), c = gc(); f * x; })
char buf[1 << 20], *p1, *p2;
struct node{
int from,to,op,flag;
}b[maxm],ans[maxm];
int n,m,k,cnt,tot;
int fa[maxn];
bool cmp1(node x,node y){
return x.op>y.op;
}
int find(int x){
return fa[x]==x ? x : (fa[x]=find(fa[x])) ;
}
void Merge(int x,int y){
int rx=find(x);
int ry=find(y);
if(rx==ry) return;
fa[rx]=ry;
}
void K1(){
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i){
int x=b[i].from;
int y=b[i].to;
int rx=find(x);
int ry=find(y);
if(rx==ry) continue;
fa[rx]=ry;
if(b[i].op==0){
b[i].flag=1;
cnt++;
}
}
}
void K2(){
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i) if(b[i].flag) Merge(b[i].from,b[i].to);
for(int i=1;i<=m;++i){
if(b[i].op) continue;
int x=b[i].from;
int y=b[i].to;
int rx=find(x);
int ry=find(y);
if(rx==ry) continue;
fa[rx]=ry;
b[i].flag=1;
cnt++;
if(cnt==k) break;
}
}
void K3(){
for(int i=1;i<=m;++i){
if(b[i].op==0) continue;
int x=b[i].from;
int y=b[i].to;
int rx=find(x);
int ry=find(y);
if(rx==ry) continue;
fa[rx]=ry;
b[i].flag=1;
}
}
void Solve(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;++i) scanf("%d%d%d",&b[i].from,&b[i].to,&b[i].op);
sort(b+1,b+m+1,cmp1);
K1();
if(cnt>k){
printf("-1
");
return;
}
int x=find(1);
for(int i=2;i<=n;++i){
if(find(i)!=x) {
printf("-1
");
return;
}
}
K2();
if(cnt<k){
printf("-1
");
return;
}
K3();
for(int i=1;i<=m;++i){
if(b[i].flag){
printf("%d %d %d
",b[i].from,b[i].to,b[i].op);
}
}
}
int main(){
Solve();
return 0;
}