Taco's Safest Route

In this problem, you are given one or more undirected graphs describing networks of passageways. Each node represents a location, and each edge is a passageway with a security level. Your task is to find the safest route from node 1 to node N for each graph, where the safety of a route is determined by the highest security level encountered along that route. You should choose the route that minimizes this maximum security level.

The input comprises multiple datasets. Each dataset starts with a line containing two integers \(N\) and \(M\), where \(N\) is the number of nodes and \(M\) is the number of passageways. Following this, there are \(M\) lines, each containing three integers \(a\), \(b\), and \(s\), representing an undirected edge between nodes \(a\) and \(b\) with security level \(s\). The end of input is indicated by a line with 0 0.

inputFormat

The input consists of multiple datasets. For each dataset:

• The first line contains two integers, \(N\) and \(M\), where \(N\) (\(1 \leq N \leq 10^5\)) is the number of nodes and \(M\) (\(1 \leq M \leq 10^5\)) is the number of passageways.
• The next \(M\) lines each contain three integers \(a\), \(b\), and \(s\), representing an edge between nodes \(a\) and \(b\) with security level \(s\).

A dataset with \(N = 0\) and \(M = 0\) marks the end of input and should not be processed.

outputFormat

For each dataset, output a single line containing one integer: the minimal possible "highest security level" encountered on any route from node 1 to node \(N\). The results should be printed in the order corresponding to the datasets in the input.

## sample

6 7
1 2 3
1 3 4
2 4 2
3 4 6
4 5 1
5 6 3
4 6 4
4 4
1 2 5
1 3 4
2 4 1
3 4 2
0 0

3
4

</p>