← 返回题目列表

Codeforces · 107/A

A. 宿舍供水

中文机器翻译题面 查看原题

开罗德国大学(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