Description

南京晓庄学院的学生宿舍楼编号从 $1$ 到 $n$。为了保障宿舍区的日常用水，学校在地下铺设了若干条供水管道，将部分宿舍楼连接起来。

每条管道都有固定的输水方向，水只能沿指定方向流动，不能反向流动；同时，每条管道都有一定的直径，它决定了该管道能够安全输送的最大水量。

由于校园供水系统的特殊设计，对于每栋宿舍楼，最多只有一条管道流入，并且最多只有一条管道流出。

新学期开始后，学校准备对宿舍区的供水设施进行升级，需要在部分宿舍楼安装水箱和水龙头。

对于一栋存在出水管道但不存在进水管道的宿舍楼，应在这里安装一个水箱。

对于一栋存在进水管道但不存在出水管道的宿舍楼，应在这里安装一个水龙头。

水从一个水箱出发，会沿着管道依次流向后续宿舍楼，最终到达与该水箱对应的水龙头。

由于每栋宿舍楼的入水管道和出水管道都至多只有一条，每个水箱都唯一对应一个水龙头，每个水龙头也唯一对应一个水箱。

为了保证供水安全，水箱输送的水量不能超过沿途任何一条管道所能承受的最大水量。因此，从一个水箱到其对应水龙头所能安全输送的最大水量，等于这条输水路径上所有管道直径的最小值。

请你找出所有水箱与其对应的水龙头，并计算每组水箱到水龙头之间能够安全输送的最大水量。

如果某个连通部分构成一个有向环，或者某栋宿舍楼没有连接任何管道，那么其中不存在需要输出的水箱---水龙头对。

Format

Input

第一行包含两个用空格分隔的整数 $n$ 和 $p$（$1\le n\le1000$，$0\le p\le n$），分别表示宿舍楼的数量和管道的数量。

接下来 $p$ 行描述这些管道。

第 $i$ 行包含三个整数 $a_i$、$b_i$ 和 $d_i$，表示有一条直径为 $d_i$ 的管道从宿舍楼 $a_i$ 通向宿舍楼 $b_i$。

满足：$1\le a_i,b_i\le n,a_i\ne b_i,1\le d_i\le10^6$。

保证对于每栋宿舍楼，最多只有一条管道进入，并且最多只有一条管道从该宿舍楼流出。

Output

第一行输出一个整数 $t$，表示水箱---水龙头宿舍楼对的数量。

接下来输出 $t$ 行，每行包含三个用空格分隔的整数 $tank_i$、$tap_i$ 和 $diameter_i$。

其中：

• $tank_i$ 表示安装水箱的宿舍楼编号；
• $tap_i$ 表示与其对应、安装水龙头的宿舍楼编号；
• $diameter_i$ 表示从该水箱到对应水龙头的路径上所有管道直径的最小值。

所有水箱---水龙头对必须按照 $tank_i$ 从小到大的顺序输出。

Samples

9 6
7 4 98
5 9 72
4 6 10
2 8 22
9 7 17
3 1 66

3
2 8 22
3 1 66
5 6 10

6 5
1 2 8
2 3 5
4 5 10
5 4 7
3 6 9

1
1 6 5

Note

在第一个样例中：

• 宿舍楼 $2$ 到宿舍楼 $8$ 的路径只有一条直径为 $22$ 的管道，因此最大安全输水量为 $22$；
• 宿舍楼 $3$ 到宿舍楼 $1$ 的路径只有一条直径为 $66$ 的管道，因此最大安全输水量为 $66$；
• 宿舍楼 $5$ 到宿舍楼 $6$ 的路径为 $5\to9\to7\to4\to6$，沿途管道直径分别为 $72,17,98,10$，最小值为 $10$。

在第二个样例中，$4\to5\to4$ 构成有向环。宿舍楼 $4$ 和 $5$ 都同时存在进水管道和出水管道，因此它们既不是水箱，也不是水龙头，不会出现在答案中。