成千上万的克隆人正在最大的帝国工厂工作，生产冲锋队装备的零件：爆能枪、防弹衣、头盔等。在最后一步中，装备需要使用 $N$ 个零件组装而成。克隆人掌握了 $M$ 种连接两个零件的方法：第 $i$ 种方法连接零件 $a_i$ 和 $b_i$，耗时 $t_i$ 秒。

当多个零件连接在一起时，它们被视为一个整体，此时无法再连接其中的任何一对零件。当然，属于不同装备部分的零件无法连接，并且始终可以使用这些方法组装装备的任何部分。如果一个零件的所有组成部分形成一个整体，无论它们在内部是如何连接的，该部分都被视为已组装完成。

为了提高生产力，工厂决定以最快的方式组装所有零件。然而，如果最快的方式不唯一，那么最终的装备看起来可能会有所不同。如果所采用的连接方法集合不同，则两种组装方式被视为不同。众所周知，只有当所有克隆人完全相同时，克隆军队看起来才威武。因此，工厂主管决定重新培训克隆人，以不同的时间应用某些方法，从而使最快的组装方式变得唯一。设应用第 $i$ 种连接方法所需的新时间为 $t_i^*$（注意，对于某些 $i$，$t_i$ 和 $t_i^*$ 的值可能相等）。应用方法所花费的时间必须是整数秒，且不能为负数。

然而，重新培训是一个复杂的过程，改变一种方法所需的时间一秒需要花费一天的时间。主管请你计算他为了使最快的组装方式唯一，需要花费的最少重新培训天数。

输入格式

第一行包含两个整数 $N$ 和 $M$：初始零件数量和连接方法数量（$1 \le N \le 20$，$0 \le M \le 1000$）。

接下来的 $M$ 行包含有关连接两个零件的方法的信息。第 $i$ 行包含三个整数 $a_i$、$b_i$ 和 $t_i$：可以连接的零件编号以及该方法所需的时间（$1 \le a_i, b_i \le N$，$a_i \neq b_i$，$1 \le t_i \le 10^6$）。

输出格式

第一行输出一个整数：主管重新培训克隆人所需的最少天数。

接下来的 $M$ 行，输出新连接方法的描述：在第 $i$ 行，输出三个整数 $a_i$、$b_i$ 和 $t_i^*$。新的连接时间 $t_i^*$ 必须是不超过 $10^9$ 的非负整数。方法必须按输入中的相同顺序输出。保证存在满足上述所有约束的解。

样例

样例输入 1

3 3
1 2 2
1 3 1
2 3 2

样例输出 1

1
1 2 2
1 3 1
2 3 3

样例输入 2

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

样例输出 2

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