题目描述

开罗德国大学（GUC）的宿舍楼编号从 $1$ 到 $n$，地下供水管道把这些楼连在一起。每条管道都有固定的方向（水只能沿该方向流动，不能倒流）和管径（表示它能承载的最大水量）。

每栋楼至多有一条管道流入、至多有一条管道流出。新学期伊始，住在宿舍的 GUC 学生 Lulu 要在各栋楼安装水箱和水龙头：有流出管道而没有流入管道的楼，要安装水箱；有流入管道而没有流出管道的楼，要安装水龙头。每个水箱会把水输送到所有能沿一串管道到达的楼；相应地，每个水龙头所在楼会接到来自某个水箱的水。

为了避免管道一周后爆裂（上学期就出过这种事），Lulu 还必须考虑管径：每个水箱输送的水量不能超过连接该水箱与对应水龙头的管道中最小的管径。Lulu 想知道每个水箱能安全输送到对应水龙头的最大水量。

输入格式

第一行包含两个用空格隔开的整数 $n$ 和 $p$（$1 \le n \le 1000$，$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 \le 10^6$）。

保证每栋楼至多有一条管道流入、至多有一条管道流出。

输出格式

第一行输出整数 $t$，表示水箱—水龙头配对的楼的对数。

接下来 $t$ 行，每行输出 $3$ 个用空格隔开的整数：$tank_i$、$tap_i$、$diameter_i$（$tank_i \ne tap_i$，$1 \le i \le t$），分别表示水箱楼、水龙头楼的编号，以及能安全输送的最大水量。所有 $t$ 行按 $tank_i$ 递增排序。

3 2
1 2 10
2 3 20

1
1 3 10

3 3
1 2 20
2 3 10
3 1 5

0

4 2
1 2 60
3 4 50

2
1 2 60
3 4 50