#5 WA

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

const int xx = 100010;

struct edge
{
	int u, v, d;
}a[xx], b[xx];//shizi,水泥;

vector<edge> p;

int t[xx];
int find(int x) { return t[x] == x ? x : t[x] = find(t[x]); }

int n, m, k, u, v, d, cnt1, cnt2, cnt;
int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= m; ++i)
	{
		cin >> u >> v >> d;
		if (d == 0) a[++cnt1] = { u,v,d };
		else b[++cnt2] = { u,v,d };
	}

	//if (k > cnt1) { cout << "no solution"; return 0; }

	for (int i = 1; i <= n; ++i) t[i] = i;

	for (int i = 1; i <= cnt1; ++i)
	{
		int x = find(a[i].u), y = find(a[i].v);
		if (x != y)
		{
			t[y] = x;

			p.push_back(a[i]);

			++cnt;
			if (cnt == k) break;
		}
	}

	if (cnt < k) { cout << "no solution"; return 0; }

	for (int i = 1; i <= cnt2; ++i)
	{
		int x = find(b[i].u), y = find(b[i].v);
		if (x != y)
		{
			t[y] = x;

			p.push_back(b[i]);

			++cnt;
			if (cnt == n - 1) break;
		}
	}

	if (cnt < n - 1) { cout << "no solution"; return 0; }

	if (find(1) != find(n)) cout << "no solution";
	else
	{
		for (int i = 0; i < p.size(); ++i)
		{
			printf("%d %d %d\n", p[i].u, p[i].v, p[i].d);
		}
	}

	return 0;
}