CF507E.Breaking Good

Breaking Good is a new video game which a lot of gamers want to have. There is a certain level in the game that is really difficult even for experienced gamers.

Walter William, the main character of the game, wants to join a gang called Los Hermanos (The Brothers). The gang controls the whole country which consists of n cities with m bidirectional roads connecting them. There is no road is connecting a city to itself and for any two cities there is at most one road between them. The country is connected, in the other words, it is possible to reach any city from any other city using the given roads.

The roads aren't all working. There are some roads which need some more work to be performed to be completely functioning.

The gang is going to rob a bank! The bank is located in city 1. As usual, the hardest part is to escape to their headquarters where the police can't get them. The gang's headquarters is in city n. To gain the gang's trust, Walter is in charge of this operation, so he came up with a smart plan.

First of all the path which they are going to use on their way back from city 1 to their headquarters n must be as short as possible, since it is important to finish operation as fast as possible.

Then, gang has to blow up all other roads in country that don't lay on this path, in order to prevent any police reinforcements. In case of non-working road, they don't have to blow up it as it is already malfunctional.

If the chosen path has some roads that doesn't work they'll have to repair those roads before the operation.

Walter discovered that there was a lot of paths that satisfied the condition of being shortest possible so he decided to choose among them a path that minimizes the total number of affected roads (both roads that have to be blown up and roads to be repaired).

Can you help Walter complete his task and gain the gang's trust?

《Breaking Good》是一款备受众多玩家期待的全新视频游戏。游戏中有一个关卡极其困难，即便是经验丰富的玩家也难以攻克。

游戏主角沃尔特·威廉姆斯（Walter William）希望加入一个名为“Los Hermanos”（兄弟帮）的帮派。该帮派掌控着整个国家，这个国家由 $n$ 座城市和 $m$ 条连接它们的双向道路组成。不存在连接某座城市与其自身的道路；任意两座城市之间至多只有一条道路。整个国家是连通的，即：通过给定的道路，可以从任意一座城市到达其他任意一座城市。

这些道路并非全部处于正常工作状态。其中一些道路还需进一步施工才能完全投入使用。

帮派即将抢劫一家银行！该银行位于第 $1$ 号城市。和往常一样，行动中最艰难的部分是从银行成功逃回帮派总部——而总部位于第 $n$ 号城市。为了赢得帮派的信任，沃尔特负责此次行动，并为此制定了一项精妙的计划。

首先，他们从第 $1$ 号城市返回总部（第 $n$ 号城市）所使用的路径必须是最短路径，因为尽快完成行动至关重要。

其次，帮派必须炸毁全国所有不在此最短路径上的道路，以阻止警方增援。若某条道路本就处于故障状态（即非工作道路），则无需炸毁——它已无法使用。

如果所选最短路径中包含某些非工作道路，则他们必须在行动前将这些道路修复。

沃尔特发现，满足“最短路径”条件的路径数量非常多；于是他决定从中选择一条能最小化受影响道路总数的路径——这里的“受影响道路”包括两类：需被炸毁的道路，以及需被修复的道路。

你能帮助沃尔特完成这项任务，从而赢得帮派的信任吗？

The first line of input contains two integers n, m (2 ≤ n ≤ 105, ), the number of cities and number of roads respectively.

In following m lines there are descriptions of roads. Each description consists of three integers x, y, z (1 ≤ x, y ≤ n, ) meaning that there is a road connecting cities number x and y. If z = 1, this road is working, otherwise it is not.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$，），分别表示城市的数量和道路的数量。

接下来的 $m$ 行描述了各条道路。每行包含三个整数 $x$、$y$、$z$（$1 \leq x, y \leq n$，），表示存在一条连接城市 $x$ 和城市 $y$ 的道路。若 $z = 1$，则该道路处于正常工作状态；否则该道路不工作。

In the first line output one integer k, the minimum possible number of roads affected by gang.

In the following k lines output three integers describing roads that should be affected. Each line should contain three integers x, y, z (1 ≤ x, y ≤ n, ), cities connected by a road and the new state of a road. z = 1 indicates that the road between cities x and y should be repaired and z = 0 means that road should be blown up.

You may output roads in any order. Each affected road should appear exactly once. You may output cities connected by a single road in any order. If you output a road, it's original state should be different from z.

After performing all operations accroding to your plan, there should remain working only roads lying on some certain shortest past between city 1 and n.

If there are multiple optimal answers output any.

第一行输出一个整数 $k$，表示受帮派影响的道路的最少可能数量。

接下来的 $k$ 行中，每行输出三个整数，描述应受影响的道路。每行包含三个整数 $x$、$y$、$z$（其中 $1 \le x, y \le n$，），分别表示由该道路连接的两座城市以及该道路的新状态。$z = 1$ 表示城市 $x$ 与 $y$ 之间的道路应被修复；$z = 0$ 表示该道路应被炸毁。

你可以以任意顺序输出这些道路。每条受影响的道路必须恰好出现一次。对于一条道路所连接的两座城市，其输出顺序可以任意。若你输出某条道路，则其原始状态必须与 $z$ 不同。

按照你的方案执行全部操作后，仅保留那些位于某条从城市 $1$ 到城市 $n$ 的特定最短路径上的道路（即其余所有道路均应失效）。

若存在多个最优解，输出任意一个即可。

In the first test the only path is 1 - 2

In the second test the only shortest path is 1 - 3 - 4

In the third test there are multiple shortest paths but the optimal is 1 - 4 - 6 - 8

在第一个测试中，唯一的路径是 $1\,-\,2$。

在第二个测试中，唯一的最短路径是 $1\,-\,3\,-\,4$。

在第三个测试中，存在多条最短路径，但最优路径是 $1\,-\,4\,-\,6\,-\,8$。