#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>g[2];
int f[20004];
int fin(int x){
	return f[x]==x?x:f[x]=fin(f[x]);
}
int n,m,k;
int check(int p){
	for(int i=1;i<=n;i++)f[i]=i;
	int cnt=0;
	for(int i=0;i<=p;i++){
		int x=g[1][i].first,y=g[1][i].second;
		if(fin(x)!=fin(y))f[fin(x)]=fin(y);
	}
	for(int i=0;i<g[0].size();i++){
		int x=g[0][i].first,y=g[0][i].second;
		if(fin(x)!=fin(y))f[fin(x)]=fin(y),cnt++;
	}
	return cnt;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		g[c].push_back({a,b});
		f[fin(a)]=fin(b); 
	}
	for(int i=1;i<=n;i++){
		if(fin(i)!=fin(1)){
			cout<<"no solution";
			return 0;
		}
	}
	int l=-2,r=g[0].size();
	while(l+1<r){
		int mid=(l+r)>>1;
		if(check(mid)>=k)l=mid;
		else r=mid;
	}
	if(l==-2||check(l)!=k){
		cout<<"no solution";
	}else{
		for(int i=1;i<=n;i++)f[i]=i;
		for(int i=0;i<=l;i++){
			int x=g[1][i].first,y=g[1][i].second;
			if(fin(x)!=fin(y)){
				f[fin(x)]=fin(y);
				cout<<x<<' '<<y<<" 1\n"; 
			}
		}
		for(int i=0;i<g[0].size();i++){
			int x=g[0][i].first,y=g[0][i].second;
			if(fin(x)!=fin(y))f[fin(x)]=fin(y),cout<<x<<' '<<y<<" 0\n";
		}
		for(int i=l+1;i<g[1].size();i++){
			int x=g[1][i].first,y=g[1][i].second;
			if(fin(x)!=fin(y)){
				f[fin(x)]=fin(y);
				cout<<x<<' '<<y<<" 1\n"; 
			}
			
		}
	}
	return 0;
}

做法：先将两种边分出来，之后二分水泥边的“生成树先用”个数，得出此时用的鹅卵石路个数。若二分得出的值存在合法方案则合法，否则非法。