本题没有可用的提交语言。

描述

某个小镇有 $n$ 个交叉路口，由双向和单向街道连接。小镇非常现代化，因此许多街道通过隧道或高架桥通行。当然，任意两个交叉路口之间都可以双向通行，即在不违反交通规则的情况下，既可以从交叉路口 $a$ 到交叉路口 $b$，也可以从 $b$ 到 $a$。由于单向街道更安全，决定尽可能多地创建单向交通。为了避免造成太多混乱，还决定不改变已有单向街道的交通方向。

你的任务是为小镇创建一个新的交通系统。你需要为尽可能多的双向街道确定交通方向，并确保任意两个交叉路口之间仍然可以双向通行。

编写一个程序完成以下任务：

从标准输入读取小镇街道系统的描述；
为每条双向街道确定一个交通方向，或决定该街道必须保持双向；
将答案输出到标准输出。

输入
输入的第一行包含两个整数 $n$ 和 $m$，其中 $2 \leq n \leq 2000$ 且 $n-1 \leq m \leq \frac{n(n-1)}{2}$。整数 $n$ 表示小镇的交叉路口数量，$m$ 表示街道数量。

接下来的 $m$ 行，每行包含三个整数 $a$、$b$ 和 $c$，其中 $1 \leq a \leq n$，$1 \leq b \leq n$，$a \neq b$，且 $c \in \{1, 2\}$。如果 $c = 1$，则表示交叉路口 $a$ 和 $b$ 之间有一条从 $a$ 到 $b$ 的单向街道；如果 $c = 2$，则表示 $a$ 和 $b$ 之间有一条双向街道。任意两个交叉路口之间最多有一条街道连接。

输出
输出的行数与输入中双向街道的数量完全相同。
对于每条双向街道（以任意顺序），程序应输出三个整数 $a$、$b$ 和 $c$，表示将街道方向改为从 $a$ 到 $b$（$c = 1$），或保持双向（$c = 2$）。如果有多个解满足单向街道数量最大化，程序可以输出其中任意一个解，但只需输出一个。

输入数据 1

4 4  
4 1 1  
4 2 2  
1 2 1  
1 3 2  

输出数据 1

2 4 1  
3 1 2  

来源
Central Europe 2002