新亚王国（Kingdom of New Asia）包含 $N$ 个村庄，由 $M$ 条道路连接。有些道路是鹅卵石路，有些是混凝土路。维护道路免费需要大量资金，王国似乎无法维护每一条道路。因此，需要一个新的道路维护计划。

国王决定，王国将尽可能少地保留免费道路，但必须保证任意两个不同的村庄之间通过免费道路有且仅有一条路径。此外，尽管混凝土路更适合现代交通，但国王认为在鹅卵石路上行走很有趣。因此，他决定恰好保留 $K$ 条鹅卵石路作为免费道路。

例如，假设新亚王国的村庄和道路如图 1a 所示。如果国王想要保留两条免费的鹅卵石路，那么王国可以保留道路 (1,2)、(2,3)、(3,4) 和 (3,5) 作为免费道路，如图 1b 所示。该计划满足国王的条件，因为 (1) 任意两个村庄之间通过免费道路有且仅有一条路径，(2) 免费道路的数量尽可能少，并且 (3) 恰好有两条鹅卵石路：(2,3) 和 (3,4)。

图 1：(a) 新亚王国村庄和道路的一个示例配置。实线表示混凝土路，虚线表示鹅卵石路。(b) 一个保留了两条免费鹅卵石路的道路维护计划。图中仅显示了免费道路。

题目描述

给定新亚王国的道路描述以及国王想要保留的免费鹅卵石路数量，编写一个程序来确定是否存在满足国王条件的道路维护计划，如果存在，则输出一个有效的计划。

输入格式

第一行包含三个由空格分隔的整数： $N$，村庄数量 ($1 \le N \le 20,000$)， $M$，道路数量 ($1 \le M \le 100,000$)，以及 * $K$，国王想要保留的免费鹅卵石路数量 ($0 \le K \le N - 1$)。

接下来的 $M$ 行描述了新亚王国的道路，道路编号为 1 到 $M$。第 $(i + 1)$ 行描述了第 $i$ 条道路，包含三个由空格分隔的整数： $u_i$ 和 $v_i$，由第 $i$ 条道路连接的两个村庄。村庄编号为 1 到 $N$。 $c_i$，第 $i$ 条道路的类型；若 $c_i = 0$，则第 $i$ 条道路是鹅卵石路；若 $c_i = 1$，则第 $i$ 条道路是混凝土路。

任意两个村庄之间最多只有一条道路。

输出格式

如果不存在满足国王条件的道路维护计划，程序应在输出的第一行打印 no solution。

否则，程序应通过列出将要保留的免费道路来输出一个有效的道路维护计划，每行输出一条道路。输出道路时，请打印输入中描述该道路的那一行。道路可以以任何顺序排列。如果存在多个有效计划，可以输出其中任意一个。

样例

样例输入 1

5 7 2
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1

样例输出 1

3 2 0
4 3 0
1 2 1
5 3 1

说明

（此输入与图 1a 一致。） （此输出与图 1b 一致。）

子任务

在分值为 20 分的测试场景中，$K$ 最多为 10。