题目描述

新亚（New Asia）王国有 \(N\) 个村庄，由 \(M\) 条道路连接。其中一些道路是鹅卵石路，而其它道路是水泥路。保持道路免费运行需要一大笔费用，并且看上去王国不可能保持所有道路免费。为此亟待制定一个新的道路维护计划。

国王已经决定保持尽可能少的道路免费，但是每两个不同的村庄之间都应该由一条且仅由一条免费道路的路径连接。同时，虽然水泥路更适合现代交通的需要，但国王也认为走在鹅卵石路上是一件有趣的事情。所以，国王决定保持刚好 \(K\) 条鹅卵石路免费。

举例来说，假定新亚王国的村庄和道路，如图 1：\((a)\) 所示。如果国王希望保持两条鹅卵石路免费，那么,可以如图 1：\((b)\) 中那样保持道路 \((1,2)\)、\((2,3)\)、\((3,4)\) 和 \((3,5)\) 免费。
该方案满足了国王的要求，因为：

(1) 每两个村庄之间都有一条由免费道路组成的路径；
(2) 免费的道路已经尽可能少；
(3) 方案中刚好有两条鹅卵石道路 \((2,3)\) 和 \((3,4)\)。

图 1：\((a)\) 新亚洲王国村庄和道路的示例配置。实线表示混凝土道路，虚线表示鹅卵石道路。 \((b)\) 一项道路维护计划，确保两条鹅卵石道路畅通无阻。仅显示免费道路。

给定一个关于新亚王国村庄和道路的描述，以及国王决定保持免费的鹅卵石道路数目，写一个程序确定是否存在一个道路维护计划以满足国王的要求，如果存在则任意输出一个方案。

输入

第一行，包含三个由空格隔开的整数：

• \(N\)，村庄的数目(\(1 \leq N \leq 2 \times 10^4\))；
• \(M\)，道路的数目(\(1 \leq M \leq 10^5\))；
• \(K\)，国王希望保持免费的鹅卵石道路数目(\(0 \leq K \leq N-1\))。

此后 \(M\) 行描述了新亚王国的道路，编号分别为 \(1\) 到 \(M\)。第 (\(i+1\)) 行描述了第 \(i\) 条道路的情况。用 \(3\) 个由空格隔开的整数描述：

• \(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

输出

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

数据范围限制

对于每组输入数据，如果你的程序输出正确便能得到 \(100\%\) 的分数，否则得 \(0\) 分。
在 \(20\) 分的测试数据中，\(K\) 的值最多为 \(10\)。

来源

APIO2008