Did you know that in autumn people work better? Just because ancients used to harvest each autumn.

Temirulan decided to travel around Woogle offices. There are some two-way paths between some of the offices. Each of those paths costs some amount of wollars. We can assume that Temirulan has an unlimited amount of wollars. Temirulan pays for the path using his Waspi card. Note that Temirulan can travel between all pairs of offices, and there is no self connecting paths. Aidana worries about Temirulan. She wants Temirulan to spend less money on this travel. She wants to set a minimum possible limit on his card (who understands these girls?), so that Temirulan won't see the difference. It means, that if Temirlan goes from office A to office B in the cheapest way (he always goes in an optimal way, ACM habit), then each his payment during travel won't be declined due to limit, for any office A and B.

Help Aidana to choose the minimum amount of wollars she can set on his card as limit and at the same time Temirulan would be able to travel from any office to any office by optimal way.

Input

In the first line given two non-negative integer numbers n, m (2 ≤ n ≤ 100, 1 ≤ m ≤ n * (n - 1) / 2) - the number of offices, and the number of paths between them.

In the next m lines given by three non-negative integer numbers v, u, w (1 ≤ v, u ≤ n, 1 ≤ w ≤ 105) - description of offices and cost of the path.

Output

Output one integer - the minimal limit for Temirulan's card.