Minimum Spanning Tree and Maximum Edge

You are given a network of villages and potential power line proposals between them. Each proposal connects two villages with a specified cost. Your task is to select a subset of proposals such that all villages are connected (i.e. the network forms a spanning tree) while minimizing the total cost. In addition, you need to determine the length of the longest power line used in this configuration.

More formally, given a graph \(G=(V,E)\) with \(|V|=n\) vertices and a list of edges \(E\) where each edge \((u,v,c)\) has a cost \(c\), find a minimum spanning tree (MST) of \(G\). Output two numbers: the sum of the costs of the edges in the MST and the maximum cost among those selected edges. The required output should be in the following LaTeX format:

Minimum Total Cost: \(\text{cost}\)
Maximum Edge in MST: \(\text{max_edge}\)

You may assume that the input graph is connected and that an MST always exists.

inputFormat

The input begins with an integer (T) (the number of test cases). Each test case starts with two integers (n) and (m), representing the number of villages and the number of power line proposals respectively. This is followed by (m) lines, each containing three integers (u), (v), and (c) -- indicating a bidirectional proposal between villages (u) and (v) with cost (c).

outputFormat

For each test case, output a single line containing two integers separated by a space: the minimum total cost to connect all villages and the length of the longest power line used in the MST.## sample

1
2 1
1 2 100

100 100