Secure Presidential Route

In the war‐torn year 2333, the world is divided between the XC and WJ alliances which are constantly at war. President ZR of Q country urgently needs to travel by car from city 1 to Yugo's capital at city n. However, the road network is unreliable – some roads are broken (denoted as 0) while others are intact (denoted as 1). As soon as the president embarks on his journey, all roads emanating from every city along his chosen route (except for the roads used in the route) must be destroyed in order to thwart an imminent enemy attack.

You, having a god’s eye view, are allowed to intervene in the network: you may repair a broken road (i.e. change its status from 0 to 1) if it is on the route, or destroy a good road (change its status from 1 to 0) if it is not on the route. Note that you cannot build any new roads that do not already exist in the map.

The final configuration should have exactly the roads used on the route as good, and all other roads (if originally good) should be turned off. Your task is to choose a simple route from city 1 to city n that minimizes the total number of operations required. The operations count is computed as follows:

• For every road on the route that is originally broken, you must repair it (cost = 1 per road).
• For every road not on the route that is originally good, you must destroy it (cost = 1 per road).

If the total number of roads that are originally good is T, and if your chosen route contains g good roads and r broken roads, then the total operations is:

Since T is constant for a given map, minimizing k is equivalent to minimizing (r - g). You are given an undirected road network with n cities and m roads (each road appears exactly once in the input). Each road is described by two endpoints u and v and its status s (either 0 or 1). There is no road from a city to itself.

Input: The first line contains two integers n and m. Each of the next m lines contains three integers u, v, and s, describing a road between cities u and v with status s.

Output: On the first line, output the minimum total number of operations k needed. On the second line, output an integer p representing the number of roads in the chosen route. Then output p lines, each containing two integers representing consecutive cities on the route (i.e. the roads that will remain working in the final configuration). It is guaranteed that a route exists.

Note: You may repair a broken road on the route or destroy a good road not on the route, even if that means modifying roads that were originally good. However, you cannot add any new roads.

inputFormat

The input begins with a line containing two space‐separated integers n and m (the number of cities and roads). Then m lines follow, each containing three integers u v s where 1 ≤ u, v ≤ n and s is either 0 (broken road) or 1 (good road).

outputFormat

Output the minimum number of operations k on the first line. On the second line, print an integer p representing the number of roads on the chosen route. The following p lines should each contain two integers representing two consecutive cities on the route (i.e. the roads that remain working after modifications).

sample

4 4
1 2 1
2 3 0
3 4 1
2 4 0

1
3
1 2
2 3
3 4