Minimum Fatigue

You are given a set of n islands and m bidirectional bridges connecting them. Each bridge connects two distinct islands and has an associated resistance level r.

John needs to travel from island 1 to island n. However, during the traversal, he experiences fatigue proportional to the highest resistance encountered on the chosen path. In other words, if a path uses several bridges with resistances, John's fatigue is determined by the maximum resistance among them. Your task is to compute the minimum possible value of this maximum resistance over all paths from island 1 to island n.

This problem can be formulated as minimizing the quantity $$\min\;\max_{bridge \in path} \; r.$$

Note: It is guaranteed that a path from island 1 to island n exists.

inputFormat

The input is given via stdin and has the following format:

n m
a1 b1 r1
a2 b2 r2
... 
am bm rm

Where:

• n is the number of islands.
• m is the number of bridges.
• Each of the next m lines contains three integers a, b, and r representing a bridge between islands a and b with resistance level r.

outputFormat

Output a single integer to stdout: the minimum possible maximum resistance level that John must tolerate to travel from island 1 to island n.

## sample

4 5
1 2 7
1 3 3
2 3 2
2 4 9
3 4 8

8