Smallest Maximum Weight Edge

You are given an undirected weighted graph with N nodes and M edges. Each edge has a weight. Your task is to determine the minimum possible value of the maximum weight edge along any path from node 1 to node N. In other words, among all the possible paths from node 1 to node N, you need to choose one such that the weight of the heaviest edge in that path is minimized. If there is no valid path from node 1 to node N, output -1.

The problem can be efficiently solved using a modified Dijkstra's algorithm where, instead of summing weights, you track the maximum edge weight encountered along the path.

Note: All edges are bidirectional.

inputFormat

The first line contains two integers N and M — the number of nodes and edges, respectively.

The next M lines each contain three integers u v w, describing an edge between nodes u and v with weight w.

outputFormat

Output a single integer on a line: the minimum possible value of the maximum edge weight along the path from node 1 to node N. If no valid path exists, print -1.

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

5