카로사이

Karosas Rosas는 $N$개의 연못으로 이루어진 연못 시스템에서 배를 타고 다닌다. 일부 연못은 서로 연결되어 있어 한 연못에서 다른 연못으로 건널 수 있다. 연결된 두 연못 사이에는 높이가 정해진 칸막이가 있으며, 이 높이를 $h_{i,j}$로 나타낸다. 이때 $h_{i,j} = h_{j,i}$이다. Karosas는 연못 $i$의 수위가 $h_{i,j}$ 이상일 때에만 연못 $i$에서 연못 $j$로 건널 수 있다. 예를 들어 연못이 3개($N = 3$)이고, 1번과 2번 연못은 높이 $h_{1,2} = 5000$인 칸막이로, 2번과 3번 연못은 높이 $h_{2,3} = 7000$인 칸막이로 연결되어 있다고 하자. 1번 연못의 수위가 5000 이상이면 Karosas는 1번에서 2번으로 건널 수 있다. 1번에서 3번으로 가려면 수위가 7000 이상이어야 한다. 그림에서 보듯 Karosas는 1번에서 2번 연못으로는 건널 수 있지만 3번 연못으로는 건널 수 없다. Karosas Rosas는 1번 연못에 머물고 있고, 그의 친구는 $N$번 연못에 있다. Rosas는 친구를 만나러 가려면 1번 연못의 수위가 얼마 이상이어야 하는지 알고 싶다. 연못 구성이 주어졌을 때, 1번 연못에서 $N$번 연못에 도달할 수 있도록 1번 연못의 수위를 최소 얼마까지 올려야 하는지 구하라.

첫 줄에 연못의 수 $N$과 연결된 연못 쌍의 수 $M$이 주어진다. 이어지는 $M$개의 줄에는 정수 $i$, $j$, $h_{i,j}$가 각각 주어진다. 이는 연못 $i$와 $j$가 높이 $h_{i,j}$인 칸막이로 연결되어 있다는 뜻이다. ($1 \le i < j \le N$, $h_{i,j} = h_{j,i}$)

1번 연못에서 $N$번 연못에 도달하는 데 필요한 1번 연못 수위의 최솟값을 정수 하나로 출력한다. 입력에서는 1번 연못에서 $N$번 연못으로 가는 경로가 항상 존재한다고 보장한다.

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