Karosai

Karosas Rosas sails on a pond system made of $N$ ponds. Some of the ponds are connected, so you can cross from one to another. Each connection has a partition with a fixed height, written $h_{i,j}$, where $h_{i,j} = h_{j,i}$. Karosas can cross from pond $i$ to pond $j$ only when the water level in pond $i$ is at least $h_{i,j}$. For example, there are three ponds ($N = 3$). Ponds 1 and 2 are joined by a partition with $h_{1,2} = 5000$, and ponds 2 and 3 are joined by a partition with $h_{2,3} = 7000$. If the water level in pond 1 is at least 5000, Karosas can cross from pond 1 to pond 2. To reach pond 3 from pond 1, the level must be at least 7000. In the picture, Karosas can get from pond 1 to pond 2 but not to pond 3. Karosas Rosas is staying in pond 1, and his friend is in pond $N$. Rosas wants to know how high the water level in pond 1 must be so that he can visit his friend. Given the pond setup, find the minimum level that pond 1 must be raised to so that pond $N$ can be reached from pond 1.

The first line contains two integers $N$ and $M$, the number of ponds and the number of connected pairs. Each of the next $M$ lines contains three integers $i$, $j$, and $h_{i,j}$, meaning ponds $i$ and $j$ are joined by a partition of height $h_{i,j}$. ($1 \le i < j \le N$, and $h_{i,j} = h_{j,i}$.)

Print one integer, the minimum water level in pond 1 needed to reach pond $N$ from pond 1. The input guarantees that a path from pond 1 to pond $N$ always exists.

$1 < N \le 1\,000$, $0 < M \le \frac{N(N-1)}{2}$, $0 < h_{i,j} \le 10^9$