Breaking Good 是一款很多游戏玩家都想拥有的新视频游戏。即使对于经验丰富的玩家来说,游戏中的某些关卡也确实很困难。
游戏主角 Walter William 想加入一个名为 Los Hermanos(兄弟)的帮派。该团伙控制了整个国家,该国家由n个城市组成,有m条双向道路连接它们。没有道路将一座城市与其自身连接起来,对于任何两个城市来说,它们之间至多只有一条道路。国家是相连的,换句话说,可以使用给定的道路从任何其他城市到达任何城市。
道路并非全部畅通。有些道路需要进行更多工作才能完全发挥作用。
这伙人要抢劫银行!银行位于城市 1。像往常一样,最困难的部分是逃到警察无法找到他们的总部。该团伙的总部位于n市。为了赢得帮派的信任,沃尔特负责这次行动,因此他想出了一个聪明的计划。
首先,他们从城市 1 返回总部 n 的路径必须尽可能短,因为尽快完成操作非常重要。
然后,该团伙必须炸毁该国所有其他不位于这条道路上的道路,以阻止任何警察增援。如果道路无法使用,他们不必炸毁它,因为它已经出现故障。
如果所选路径中有一些道路无法使用,他们必须在操作之前修复这些道路。
Walter发现有很多条路径满足尽可能最短的条件,因此他决定在其中选择一条使受影响道路总数(包括需要炸毁的道路和需要修复的道路)总数最少的路径。
你能帮助沃尔特完成他的任务并赢得帮派的信任吗?
输入
输入的第一行包含两个整数 n, m (2 ≤ n ≤ 105, $$0 \leq m \leq \min\left(\frac{n(n-1)}{2}, 10^5\right)$$),分别为城市数和道路数。
接下来的m行有道路的描述。每个描述由三个整数 x, y, z (1 ≤ x, y ≤ n, $$z \in \{0, 1\}$$) 组成,表示有一条道路连接城市编号 x 和 y。如果 z = 1,则这条路有效,否则无效。
输出
在第一行输出一个整数k,即受帮派影响的最小可能道路数。
在下面的 k 行中输出三个整数,描述应该受到影响的道路。每行应包含三个整数 x, y, z (1 ≤ x, y ≤ n, $$z \in \{0, 1\}$$)、道路连接的城市以及道路的新状态。 z = 1 表示城市 x 和 y 之间的道路应修复,z = 0 表示道路应炸毁。
您可以按任何顺序输出道路。每条受影响的道路应该恰好出现一次。您可以按任意顺序输出由单条道路连接的城市。如果你输出一条道路,它的原始状态应该与z不同。
根据您的计划执行所有操作后,应该仅在城市 1 和 n 之间的某些最短过去的道路上保持工作状态。
如果有多个最佳答案,则输出任意一个。
示例
输入 #1
2 1 1 2 0
输出 #1
1 1 2 1
输入 #2
4 4 1 2 1 1 3 0 2 3 1 3 4 1
输出 #2
3 1 2 0 1 3 1 2 3 0
输入 #3
8 9 1 2 0 8 3 0 2 3 1 1 4 1 8 7 0 1 5 1 4 6 1 5 7 0 6 8 0
输出 #3
3 2 3 0 1 5 0 6 8 1
注意
在第一个测试中,唯一的路径是 1 - 2
在第二次测试中,唯一的最短路径是 1 - 3 - 4
在第三次测试中,有多个最短路径,但最佳路径是 1 - 4 - 6 - 8