开罗德国大学(GUC)宿舍的编号为1到n。地下水管将这些房屋连接在一起。每根管道都有一定的方向(水只能沿该方向流动,反之亦然)和直径(表征其可以处理的最大水量)。
每栋房子最多有一根管子进入,最多有一根管子出去。新学期开始,GUC学生兼宿舍居民露露想在宿舍安装水箱和水龙头。对于每一个有出水管但没有进水管的房子,露露应该在该房子安装一个水箱。对于每一个有进水管但没有出水管的房子,露露应该在该房子安装一个水龙头。每个水箱房都会将水输送到所有从水箱到它有一系列管道的房屋。因此,每个水龙头房都将接收来自某个水箱房的水。
为了避免一周后水管爆裂(就像上学期那样),露露还得考虑水管的直径。每个水箱输送的水量不应超过连接水箱与其相应水龙头的管道直径。露露想要找到可以安全地从每个水箱输送到相应水龙头的最大水量。
输入
第一行包含两个空格分隔的整数 n 和 p (1 ≤ n ≤ 1000, 0 ≤ p ≤ n) — 相应的房屋数量和管道数量。
接下来是 p 行 — p 管道的描述。第i行包含三个整数ai bi di,表示从ai房屋到bi房屋的直径为di的管道(1≤ai,bi≤n,ai≠bi,1≤di≤106)。
保证每栋房子最多有一根管子进,最多有一根管子出。
输出
在第一行打印整数 t — 房屋的水箱龙头对的数量。
对于接下来的 t 行,每行打印 3 个整数,用空格分隔:tanki、tapi 和直径i,其中 tanki ≠ tapi (1 ≤ i ≤ t)。这里tanki和tapi分别是水箱和水龙头的索引,直径i是可以输送的最大水量。所有 t 行都应该由 tanki 订购(越来越多)。
示例
输入 #1
3 2 1 2 10 2 3 20
输出 #1
1 1 3 10
输入 #2
3 3 1 2 20 2 3 10 3 1 5
输出 #2
0
输入 #3
4 2 1 2 60 3 4 50
输出 #3
2 1 2 60 3 4 50