Stable Network

A company has one headquarters computer and several branch computers. The headquarters computer is always computer 1, and it is directly connected to every branch computer. Some pairs of branch computers may also be directly connected.

Two computers are considered connected if they can communicate either directly or through other computers.

The company wants the network to remain connected after a failure. If one direct connection between two computers is cut, those two computers must still be connected through another route. If one computer fails, all computers that did not fail must still be connected to each other.

You are given the existing connections between branch computers and the cost of adding each possible connection. Determine whether the network is already stable. If it is not, add connections between branch computers with minimum total cost so that the network becomes stable.

The first line contains two integers n and m. n is the number of computers, and m is the number of already directly connected pairs of branch computers. (1 <= n <= 1000, 0 <= m <= 10000)

Each of the next m lines contains two different branch computers x and y, meaning that computers x and y are directly connected.

The next n lines contain an adjacency matrix of connection costs. The cost of connecting two different computers is an integer from 1 to 30000, and the cost from computer i to computer j is the same as the cost from computer j to computer i. The headquarters computer is always computer 1.

On the first line, print the minimum additional cost X and the number of added connections K.

On each of the next K lines, print the numbers of two branch computers that should be directly connected. If the given network is already stable, print X = 0 and K = 0.

If several minimum-cost answers exist, you may print any one of them.