Problem A. Road repairing ≡

Author:Timofey S. Chistyakov   Time limit:5 sec
Input file:input.txt   Memory limit:6 Mb
Output file:output.txt  

Statement

A city road network contains N intersections connected with M roads. It is possible to reach any intersection from any other. Before winter started, city major decided to repair some roads in the city, so they wouldn't be totally ruined by spring time.

However, due to magnificent celebration of the city anniversary, city budget is considerably exhausted. That is why city administration wants to repair as little roads as possible. Some roads are already in satisfactory condition and don't need repairing. As to the other roads, the major wants to repair only those that cannot be driven around, even by the bad roads.

Your task is to help the major to obtain the list of the roads that are to be repaired.

Input file format

Input file contains numbers N M, then M triads of numbers ai, bi, ci. Each triad describes one road connecting intersections ai, bi. ci is 1 if the road is in satisfactory condition and 0 otherwise.

Output file format

Output file should contain the number of roads to be repaired, then the list of these roads. Each road should be described by two numbers of connected intersections. The roads should be sorted by first intersection, secondary sorted by second intersection. Within each road description the intersection with less number should come first.

Constraints

1 ≤ N, M ≤ 100000,

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
7 8
1 2 0
2 3 1
1 3 0
2 4 1
5 3 0
5 6 1
6 7 0
5 7 0

1 3 5
0.207s 0.009s 15