CF507E Breaking Good

Breaking Good 是一款新推出的视频游戏，许多玩家都想拥有它。游戏中有一个关卡，即使是经验丰富的玩家也觉得非常困难。 游戏的主角 Walter William 想要加入一个名叫 Los Hermanos（意为“The Brothers”）的帮派。该帮派控制着整个国家，国家由 $n$ 座城市 和 $m$ 条双向道路连接。没有道路连接同一座城市，任意两座城市之间最多只有一条道路。这个国家是连通的，也就是说，利用现有的道路可以从任意一个城市到达另一个城市。 并非所有道路都在正常运作，有些道路还需要进一步的修理才能完全通行。 帮派打算抢劫一家银行！银行位于城市 $1$。像往常一样，最难的部分是逃回他们的总部，让警察无法捉到他们。帮派的总部位于城市 $n$。为了赢得帮派的信任，Walter 负责此次行动，他制定了一个聪明的计划。 首先，他们在银行得手之后，从城市 $1$ 回到总部 $n$ 的路径必须尽可能短，因为必须尽快结束行动。 然后，帮派必须炸毁所有不在该路径上的其它道路，以防止警方增援。如果是坏掉的路，则不需要再炸毁，因为它本身就是不通的。 如果选定的最短路径上有不工作的道路，他们需要在行动前将其修复。 Walter 发现，满足最短路径条件的方案有很多，所以他决定从中选择使“受影响道路总数”（既需要炸毁的道路加上需要修理的道路）最少的那个。 你能帮助 Walter 完成任务，赢得帮派的信任吗？

输入的第一行包含两个整数 $n, m$（$2 \leq n \leq 10^{5}$，$1 \leq m \leq 2 \times 10^5$），分别表示城市数量和道路数量。 接下来的 $m$ 行，每行包含三个整数 $x, y, z$（$1 \leq x, y \leq n$，$x \neq y$），表示有一条连接城市 $x$ 和 $y$ 的道路。如果 $z = 1$，则该道路可用；否则该道路不可用。

输出第一行是一个整数 $k$，即帮派需要影响的最少道路数量。 接下来的 $k$ 行，每行包含三个整数 $x, y, z$（$1 \leq x, y \leq n$，$x \neq y$），表示应被影响的道路的两端城市以及该道路的新状态。$z = 1$ 表示该道路应被修理为可用，$z = 0$ 表示该道路应被炸毁。 你可以以任意顺序输出这些道路。每条被影响的道路只能输出一次。对于每一条你输出的道路，它的初始状态应与 $z$ 不同。 经过所有操作后，只允许存在且可用的道路是在某条从城市 $1$ 到城市 $n$ 的最短路径上的。 如果存在多组最优答案，输出任意一组即可。

在第一个测试中，唯一的路径是 $1-2$。 在第二个测试中，唯一的最短路径是 $1-3-4$。 在第三个测试中，存在多条最短路径，但最优的是 $1-4-6-8$。 由 ChatGPT 5 翻译