To get straight to the point, it is sufficient to take a minimum spanning tree of the weighted perfected graph with edge weights \(w_{i, j} = A_{i, j}\), and check if it satisfies the condition in the problem statement.

Proof

Let \(T\) be such a minimum spanning tree. Suppose that there is a different but valid tree \(U\).

Then this tree \(U\) should contain (distinct) edges \((u, v)\) and \((x, y)\) such that adding edge \((u, v)\) to, and removing edge \((x, y)\) from \(U\) makes the total weight not greater. Then \(A_{u,v} \le A_{x, y}\).

Also, the graph obtained by adding edge \((u, v)\) to tree \(U\) has exactly one cycle, and vertices \(u, v, x, y\) must be contained in this cycle (although some of the variables may refer to the same vertex). Since the path on a tree is unique, the \(u-v\) path on tree \(U\) must contain edge \((x, y)\), so \(A_{u, v} \gt A_{x, y}\).

This is a contradiction.

Hence, no tree other than \(T\) is eligible for an answer, so it is sufficient to verify this tree.

In most languages, you should be able to solve the problem using an algorithm to find a minimum spanning tree in \(O(N^2)\) time; moreover, \(O(N^2 \log N)\) algorithms will probably be accepted too. (If it leads to TLE, try to use bucket sort instead, to reduce the complexity to \(O(N^2+ \max A)\).)

The verification can be done in the same way as described in the official editorial.