The regime of a small but wealthy dictatorship has been abruptly overthrown by an unexpected rebellion. Because of the enormous disturbances this is causing in world economy, an imperialist military super power has decided to invade the country and reinstall the old regime.
For this operation to be successful, communication between the capital and the largest city must be completely cut. This is a difficult task, since all cities in the country are connected by a computer network using the Internet Protocol, which allows messages to take any path through the network. Because of this, the network must be completely split in two parts, with the capital in one part and the largest city in the other, and with no connections between the parts.
There are large differences in the costs of sabotaging different connections, since some are much more easy to get to than others.
Write a program that, given a network specification and the costs of sabotaging each connection, determines which connections to cut in order to separate the capital and the largest city to the lowest possible cost.
The first line of the input has two parts, separated by a space: First the number of cities, n in the network, which is at most 50. Then the total number of connections, m, at most 500.
The following m lines specify the connections. Each line has three parts separated by spaces: The first two are the cities tied together by that connection (numbers in the range 1-n). Then follows the cost of cutting the connection (an integer in the range 1-40000000). Each pair of cites can appear at most once in this list.
The capital is city number 1, and the largest city is number 2.
The output should be the pairs of cities (i.e. numbers) between which the connection should be cut (in any order), each pair on one line with the numbers separated by a space.
5 8 1 4 30 1 3 70 5 3 20 4 3 5 4 5 15 5 2 10 3 2 25 2 4 50
4 1 3 4 3 5 3 2