Minimum Maximum Road Weight

You are given an undirected graph with N nodes and M roads. Each road is represented by three integers u, v, and w, meaning there is a road between node u and node v with weight w.

Your task is to select a subset of these roads such that all nodes become connected (i.e. a spanning tree is formed) and the maximum weight among the chosen roads is as small as possible. If it is impossible to connect all nodes with the available roads, output -1.

This problem can be modeled as finding a Minimax Spanning Tree where the objective is to minimize the maximum edge weight in the spanning tree.

Formally, let \(G=(V, E)\) be an undirected, weighted graph. Find a subset \(E'\subseteq E\) that connects every vertex and minimizes \(\max_{e\in E'} w(e)\). If no such subset exists, output \(-1\).

inputFormat

The input is given via standard input (stdin) and has the following format:

N M
u1 v1 w1
u2 v2 w2
... 
uM vM wM

Here:

• N is the number of nodes.
• M is the number of roads.
• Each of the following M lines contains three integers u, v, and w representing a road between nodes u and v with weight w.

outputFormat

Output a single integer to standard output (stdout):

• If a spanning tree that connects all nodes exists, output the minimized maximum weight among the selected roads.
• If it is impossible to connect all nodes, output -1.

## sample

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

3