Network Recovery

There is a network of N (1 <= N <= 1,000) computers. Some pairs of computers are directly connected by communication lines, and two computers can communicate either through a direct line or through paths that pass through other computers.

Each line can have a different communication time. Using one direct line costs that line's time, and using several lines costs the sum of their times. Sometimes a path through other computers can be faster than a direct line.

After an intrusion, the administrator blocked every computer and line. Because of version limitations, the security system can be installed only on one supercomputer, computer 1. When any computer is attacked, the event is sent through the network to the supercomputer, and the supercomputer sends security packets back through the network. When restoring the network, the following conditions must hold.

1. Since another attack is possible, the number of restored lines must be as small as possible. However, after restoration, every pair of different computers must still be able to communicate.
2. For every computer, the shortest communication time from the supercomputer must not become larger than it was in the original network.

Given the original network, output one way to restore it while satisfying these conditions.

The first line contains two integers N and M. Each of the next M lines contains three integers A, B, and C, meaning that computers A and B are connected by a line whose communication time is C (1 <= C <= 10). Computers are numbered from 1 to N, and computer 1 is the supercomputer where the security system is installed. Every line is bidirectional.

Print K, the number of lines to restore, on the first line. Then print K lines, each containing two integers A and B, meaning that the line connecting computers A and B is restored. The lines may be printed in any order. If there are multiple valid answers, print any one of them.