There are several roads between cities 1, 2, ...,n. The length of each road is known. The road network is connected, i.e., there is a path between any pair of cities. Gas stations are located only in the cities. You have to calculate what is the maximal distance that the car should be able to pass in order to have no problems driving between cities.

The first line of the input contains two integers $n, k\ (1 ≤n≤ 1 ,500, 1 ≤k≤ 400 ,000)$ — the number of cities and the number of roads, respectively. 

Next $k$ lines contain the description of the roads, one per line. A line contains the pair of cities connected by the road and the distance $d_i$ between them $(0 ≤d_i≤ 10 ,000)$.

The output should contain one integer — the longest distance the car should be able to pass without refuel.