undirected graph has scanning trees. The minimal scanning tree is the scanning tree with the minimal sum of weights on edges. The minimal scanning tree can be found by using Prim's algorithm .

Write a program using C++ to find the minimal scanning tree of a graph. The graph is represented by an adjacency matrix. The adjacency matrix of a graph G =

For example, the adjacency matrix of the following graph is on its right side:

The following is Prim's algorithm:

The input of your program should be in the following format:

For example, the input corresponding to the above graph is:

5 1

0 1 3 -1 -1

1 0 3 6 -1

3 3 0 4 2

-1 6 4 0 5

-1 -1 2 5 0

Note that infinity is represented by -1.

The output of your program should be the adjacency matrix of the minimal spanning tree.

For example, the output for the above input is:

0 1 3 -1 -1

1 0 -1 -1 -1

3 -1 0 4 2

-1 -1 4 0 -1

-1 -1 2 -1 0