P1031雨霖铃（rainbell）

【题目背景】

猜灯的夜晚过去以后，春雨悄然落在花庭。Ehundategh 与 ESC 共撑一把伞走过檐下，他想起自己曾经连一句挽留都不敢说出口，于是把那时的心事写成一阕词：

《雨霖铃·春日吟思于卧》

千峰点翠，火霞焰尽，静雨轻莅。密密沉水微揽，拢云雾，彩光流瀑。几许瑶池相会，难解逢中意。恋记记、如烟妄去，天光荡散湖心影。

匿情难赠梦里人，愈缠系，愿君拾胸臆。桂花扬枝满路，终焉暮，惶惶惊鹿。贴端镜前，理或纤思细虑绵绵，又展笺、纵泪墨血，提笔落难言。

ESC 读完后把伞轻轻向他那一侧偏去。如今他们不必再隔着雨幕猜测彼此的心意，只需要一起修好花庭中的道路，让往后的每一次散步都能并肩走得更远。

【题目描述】

花庭中共有 $n$ 座花亭，编号为 $1\sim n$，另有 $m$ 条可以双向通行的道路连接其中两座花亭。同一对花亭之间可能有多条道路。雨停以后，二人打算从这些道路中选出一部分长期维护，作为每天共同散步的路线。

每条道路分为两类。在春雨中能够听见铃音的道路称为听雨路，其类型为 $0$。会在雨后映出晴光的道路称为晴光路，其类型为 $1$。

他们希望被选道路能够连接所有花亭，同时不形成任何环。这样无论二人从哪一座花亭出发，想到另一座花亭看花时，都恰好只有一条完全由被选道路组成的路径，不必在岔路前停下来重新选择方向。

ESC 喜欢听雨落在青石上的声音，Ehundategh 则记得 ESC 偏爱雨后透过枝叶的晴光。为了让两种景色都留在往后的日常里，他们要求被选道路中恰好有 $k$ 条听雨路。

请你判断这样的方案是否存在。若存在，输出任意一种符合要求的方案。否则说明无解。

【输入格式】

从文件 $\textbf{\textit{rainbell.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据。对于每组测试数据：

第一行包含三个整数 $n,m,k$，分别表示花亭数、道路数和要求选出的听雨路数量。

接下来 $m$ 行，每行包含三个整数 $u_i,v_i,t_i$，表示第 $i$ 条道路连接花亭 $u_i$ 与 $v_i$。若 $t_i=0$，这条道路是听雨路。若 $t_i=1$，这条道路是晴光路。

【输出格式】

输出到文件 $\textbf{\textit{rainbell.out}}$ 中。

对于每组测试数据：

若不存在符合要求的方案，输出一行字符串 no solution。

否则输出 $n-1$ 行，每行包含三个整数 $u,v,t$，表示选择输入中连接花亭 $u,v$ 且类型为 $t$ 的道路。道路的输出顺序任意。

【样例 1 输入】

10 224 5 231 2 042 3 053 4 161 4 171 3 183 2 191 2 1102 3 1

【样例 1 输出】

11 2 022 3 033 4 14no solution

【说明/提示】

【样例 1 解释】

第一组测试数据中，样例输出选择的三条道路连接了所有花亭，其中恰有两条听雨路，并且任意两座花亭之间都只有一条由所选道路组成的路径。

第二组测试数据中不存在听雨路，因此无法选出恰好一条听雨路。

【样例 2】

见选手目录下的 $\textbf{\textit{rainbell/rainbell2.in}}$ 和 $\textbf{\textit{rainbell/rainbell2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{rainbell/rainbell3.in}}$ 和 $\textbf{\textit{rainbell/rainbell3.ans}}$。

该组样例符合测试点 $5\sim 8$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{rainbell/rainbell4.in}}$ 和 $\textbf{\textit{rainbell/rainbell4.ans}}$。

该组样例符合测试点 $9\sim 12$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{rainbell/rainbell5.in}}$ 和 $\textbf{\textit{rainbell/rainbell5.ans}}$。

该组样例符合测试点 $13\sim 16$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{rainbell/rainbell6.in}}$ 和 $\textbf{\textit{rainbell/rainbell6.ans}}$。

该组样例符合测试点 $17\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 20$，$1\leq n\leq 2\times 10^4$，$1\leq m\leq 10^5$，$0\leq k\leq n-1$，$1\leq u_i,v_i\leq n$，$u_i\neq v_i$，$t_i\in\{0,1\}$。单个测试点内所有测试数据的 $n$ 之和不超过 $2\times 10^4$，$m$ 之和不超过 $10^5$。

特殊性质 A：保证 $k\in\{0,n-1\}$。

特殊性质 B：在所有可行方案中，听雨路数量的最小值恰好为 $k$。

特殊性质 C：在所有可行方案中，听雨路数量的最大值恰好为 $k$。