Maximum Edge in Minimum Spanning Tree

Given an undirected weighted graph representing cities and railway tracks, your task is to compute the maximum edge weight in the Minimum Spanning Tree (MST) of the graph. The graph is defined by \( n \) vertices (cities) and \( m \) edges (tracks). The MST is a spanning tree whose total weight is minimum among all spanning trees. The answer is the maximum weight among the edges chosen in the MST.

You are guaranteed that the given graph is connected for each test case, and if there are no tracks (i.e. \( m = 0 \)), the output should be 0.

The input consists of one or more test cases. Each test case begins with a line containing two integers \( n \) and \( m \). This is followed by \( m \) lines, each containing three integers \( u \), \( v \), and \( w \) indicating there is an edge between vertices \( u \) and \( v \) with weight \( w \). A test case with \( n = 0 \) and \( m = 0 \) terminates the input.

inputFormat

The input is read from standard input (stdin) and contains multiple test cases. Each test case starts with a line containing two integers \( n \) and \( m \) where \( n \) is the number of cities (vertices) and \( m \) is the number of railway tracks (edges). Following this, there are \( m \) lines each with three integers \( u \), \( v \), and \( w \) representing an edge from city \( u \) to city \( v \) with weight \( w \). The input is terminated by a test case with "0 0".

outputFormat

For each test case, output a single line containing one integer: the maximum edge weight in the Minimum Spanning Tree of the given graph, printed to standard output (stdout).

4 5
0 1 10
0 2 6
0 3 5
1 3 15
2 3 4
0 0

10