Maximum Edge in Minimum Spanning Tree

You are given an undirected weighted graph with n nodes and m edges. Your task is to compute the maximum weight among the edges that are selected in the Minimum Spanning Tree (MST) of the graph. If the graph is disconnected such that no MST exists, output -1.

The MST of a graph is a spanning tree whose sum of edge weights is as small as possible. Formally, given a graph \(G=(V,E)\) with weight function \(w: E \to \mathbb{Z}\), an MST is a subset \(T \subseteq E\) that connects all vertices with no cycles and minimizes \(\sum_{e \in T} w(e)\). In this problem, you need to report the maximum weight among all edges in \(T\).

If an MST cannot be formed because the graph is disconnected, output -1.

inputFormat

The first line contains two integers n and m, representing the number of nodes and the number of edges respectively.

The following m lines each contain three integers u, v, and w denoting an edge between node u and node v with weight w. It is guaranteed that nodes are numbered from 1 to n.

outputFormat

Output a single integer: the maximum weight among the edges in the MST. If the MST cannot be formed, output -1.

4 5
1 2 5
1 3 3
2 4 2
3 4 4
2 3 1

3