Maximizing Subcomponents' Value in a Spanning Tree

Given an undirected weighted graph with N nodes and M edges, where each node is assigned a value, your task is to select a spanning tree of the graph.

A spanning tree T of a graph \( G=(V,E) \) satisfies the property \( |T| = |V| - 1 \). In this problem, after constructing the spanning tree, if any one edge is removed, the tree will split into two connected subcomponents. Your objective is to maximize the sum of the values of the nodes in the two largest subcomponents after the removal of any edge. It turns out that constructing a Minimum Spanning Tree (MST) using Kruskal's algorithm yields one of the acceptable solutions for this problem.

Note that although each node has a value, the MST is constructed based solely on the weights of the edges.

inputFormat

The input begins with a line containing two integers N and M, representing the number of nodes and edges respectively.

The second line contains N integers where the i-th integer denotes the value of node i.

Each of the following M lines contains three integers \( u \), \( v \), and \( w \) indicating that there is an edge between nodes \( u \) and \( v \) with weight \( w \).

outputFormat

Print exactly N-1 lines. Each line should contain two integers representing an edge of the spanning tree, separated by a space. The order of the edges is not important.

## sample

6 7
3 5 2 6 1 10
1 2 4
1 3 3
2 4 2
2 5 9
3 6 8
4 6 7
5 6 1

1 2
1 3
2 4
4 6
5 6

</p>