← 返回题目列表

Codeforces · 507/E

E. 破坏良好

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

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