MY EXPENSIVE DEPOSIT

We are given the road network of the country. There are N cities (numbered from ~1~ to N) and M bidirectional roads connecting pairs of different cities. For each road, we know the quantity of gasoline (in liters) needed for a car to travel from one end to the other. Assume that there is at least one route, possibly consisting of more than one road, connecting any city to any other.

Let the fuel tank capacity of our car be L liters. We can fill it up at any gas station, but unfortunately, all gas stations are located in the cities—there are no gas stations along the roads! Therefore, to move along a road, the amount of gasoline required for the trip must be less than or equal to L.

Find the minimum possible value of L that allows us to travel by car from any city in the country to any other.

Problem

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that reads the data of the road network and prints the minimum value of ~L~ that allows us to travel from any city to any other.

Input Files:

The input files with the name smalltank.in are text files structured as follows: The first line of the input will contain two natural numbers N and M, separated by a space: the number of cities and the number of roads.

Each of the next M lines describes a bidirectional road. It contains three integers U~\mathbf{_i}~, V~\mathbf{_i}~, and W~\mathbf{_i}~, separated by spaces. Such a line means that we can travel from city U~\mathbf{_i}~ to city V~\mathbf{_i}~ (or vice versa), and for this journey, we need W~\mathbf{_i}~ liters of gasoline.

Output Files:

The output files named smalltank.out are text files with the following structure. They contain exactly one line containing an integer: the minimum fuel tank size that allows us to travel from any city to any other.

Constraints:

• 2 ~\le~ Ν ~\le~ 10.000
• 1 ~\le~ M ~\le~ 100.000
• 1 ~\le~ ~U_i~ ~\le~ N, 1 ~\le~ Vi ~\le~ N
• 1 ~\le~ ~W_i~ ~\le~ 100.000
• There will be at most one road directly connecting two cities.

Examples of Input - Output Files:

STDIN (smalltank.in)

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

STDOUT (smalltank.out)

7

Explanation:

The example is that of the above diagram. There is no way to go from city 3 to city 4 without passing through a road that requires at least 7 liters of gasoline. Therefore, the minimum L cannot be less than 7. By examining all pairs of starting and destination cities, we conclude that 7 is sufficient to move anywhere.

Notes:

Formatting: In both the input and the output, each line terminates with a newline character.
Maximum execution time: 1sec.
Maximum available memory: 64MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: smalltank *)

for PASCAL coders

/* USER: username
LANG: C
TASK: smalltank */

for C coders

/* USER: username
LANG: C++
TASK: smalltank */

for C++ coders

/* USER: username
LANG: Java
TASK: smalltank */

for Java coders

# USER: username
# LANG: Python
# TASK: smalltank

for Python coders