#include<bits/stdc++.h>

#define int long long
#define mem(x,y) memset(x,y,sizeof(x))
#define frein freopen("in.in","r",stdin)
#define freout freopen("out.out","w",stdout)
#define debug(x) cout << (#x) << " = " << x << endl;

using namespace std;

int read(){
   int s = 0,w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

struct node{
	int x;
	int y;
	int w;
	bool flag;
}e[10000010];

int n,m,k;
int pre[10000010];
int cnt;
int tot;
int siz;

vector <pair<int,int>> q;
vector <int> ans;
vector <int> ans1;

void init(){for(int i = 1;i <= n;i ++)pre[i] = i;}

int find(int x){
	if(pre[x] == x)return x;
	return pre[x] = find(pre[x]);
}

bool cmp(node x,node y){return x.w < y.w;}

bool cmp1(node x,node y){return x.w > y.w;}

signed main(){
	cin>>n>>m>>k;
	for(int i = 1;i <= m;i ++)e[i].x = read(),e[i].y = read(),e[i].w = (read() ^ 1);
	init();
	for(int i = 1;i <= m;i ++)pre[find(e[i].x)] = find(e[i].y);
	int v = find(1);
	for(int i = 2;i <= n;i ++){
		if(find(i) != v){
			puts("no solution");
			return 0;
		}
	}
	init();
	sort(e + 1,e + m + 1,cmp);
	for(int i = 1;i <= m;i ++){
		int xx = find(e[i].x);
		int yy = find(e[i].y);
		if(xx != yy){
			if(e[i].w == 1){
				q.push_back({e[i].x,e[i].y});
				ans1.push_back(i);
				e[i].flag = true;
				tot ++;
			}
			pre[xx] = yy;
			cnt ++;
		}
	}
	v = find(1);
	for(int i = 2;i <= n;i ++){
		if(find(i) != v){
			puts("no solution");
			return 0;
		}
	}
	init();
	siz = q.size();
	if(siz > k){
		puts("no solution");
		return 0;
	}
	if(siz){
		for(int i = 0;i <= siz - 1;i ++){
			int x = q[i].first;
			int y = q[i].second;
			pre[find(x)] = find(y);
		}
	}
	sort(e + 1,e + m + 1,cmp1);
	cnt = tot;
	for(int i = 1;i <= m;i ++){
		if(e[i].flag)continue;
		if(e[i].w == 1 && tot >= k)continue;
		int xx = find(e[i].x);
		int yy = find(e[i].y);
		if(xx != yy){
			pre[xx] = yy;
			if(e[i].w == 1)tot ++;
			cnt ++;
			ans.push_back(i);
			if(cnt == n - 1)break;
		}
	}
	v = find(1);
	for(int i = 2;i <= n;i ++){
		if(find(i) != v){
			puts("no solution");
			return 0;
		}
	}
	if(cnt != n - 1)puts("no solution");
	else {
		siz = ans1.size();
		if(siz)for(int i = 0;i <= siz - 1;i ++)printf("%lld %lld %lld\n",e[ans1[i]].x,e[ans1[i]].y,e[ans1[i]].w ^ 1);
		siz = ans.size();
		if(siz)for(int i = 0;i <= siz - 1;i +  +)printf("%lld %lld %lld\n",e[ans[i]].x,e[ans[i]].y,e[ans[i]].w ^ 1);
	}
}

WA 1 2 4 5 不懂