Breaking Good

题意翻译

Breaking Good这个游戏对于有经验的玩家来说也有一定的难度。 游戏的主角小明希望加入一个叫斧头帮的犯罪团伙。这个团伙控制着整个国家n个城市间的m条双向道路，这些道路保证没有自环和重边，任何城市可以通过这些道路到达任何其他城市。 然而道路并不全都能通行，有些道路是需要修复。 现在这个团伙要搞一个大新闻！搞事地点位于城市1。像往常一样，这个行动最难的部分是搞事后如何逃到他们在城市n的总部。为了获得该团伙的信任，小明决定负责这项搞事行动，而且他提出了一个看起来很明智的计划。 首先，他们将在从城市1返回途中使用的路径总长度必须尽可能短；然后，为了让搞的大新闻更加刺激，他们必须炸毁所有不在这条路径上的其他道路。但是他们不必炸掉不能通行的道路。 如果选择的道路有一些不能通行的道路，他们将不得不在行动之前修复那些道路。 小明发现，有很多路径满足了条件1（即尽可能短），所以他决定在其中选择一条路径，使受影响道路的总数最小化。 你能帮助小明完成搞事并获得该团伙的信任吗？ 输入 第一行两个整数n,m(2<=n<=10^5,0<=m<=min(n*(n-1)/2,10^5)) 下面m行每行描述一条道路，每行三个整数x,y,z(1<=x,y<=n,z∈{0,1})，x,y表示连接的城市编号，z表示此道路是否可以通行（z=1表示可以通行） 输出 第一行为一个整数k，表示影响道路的最小总数 下面k行每行描述一条道路，每行三个整数x,y,z(1<=x,y<=n,z∈{0,1})，x,y表示连接的城市编号，z=1表示此道路应该修复，z=0表示此道路应该被炸毁 （似乎有spj） 由 @守望 提供翻译

题目描述

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?

输入输出格式

输入格式

The first line of input contains two integers $ n,m $ ( $ 2<=n<=10^{5} $ , ), 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.

输出格式

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.

输入输出样例

输入样例 #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

说明

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 $