Hiking Journey

You are given a set of hiking trails connecting several mountain peaks. Each trail connects two peaks and has an associated difficulty rating. Your task is to choose a path from peak 1 to peak n such that the maximum difficulty rating encountered on the path is minimized. In other words, among all possible paths from the first to the last peak, you need to find one where the hardest trail is as easy as possible.

Formally, you are given an integer n representing the number of peaks and an integer m representing the number of trails. Each trail is described by three integers u, v and d, where u and v are the endpoints of the trail and d is its difficulty. Determine the minimum possible value of the maximum difficulty rating along any path from peak 1 to peak n.

inputFormat

The input is given via standard input (stdin). The first line contains two integers n and m — the number of peaks and the number of trails, respectively. Each of the following m lines contains three integers u, v, and d, where a trail connects peak u with peak v with difficulty rating d.

outputFormat

Output a single integer to standard output (stdout) — the minimum possible maximum difficulty rating on a path from peak 1 to peak n.

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

5