Problem Description

Takahashi doesn't particularly like buses. However, as a member of society, he cannot avoid using them.

Once he becomes a working professional, he will have to commute to his company by bus from his home. Since Takahashi hasn't received a job offer yet, he doesn't know where the company will be located.

Takahashi always anticipates the worst-case scenario, which is the longest time he might spend on a bus. He wants to move to a place where this worst-case bus ride time is as short as possible.

Note: The worst-case scenario refers to the situation where the company is located at a position that results in the longest total bus ride time when choosing the bus routes that minimize the total ride time. Also, Takahashi can choose which buses to take when commuting to the company, and he will always choose the route that minimizes the total bus ride time.

Each bus runs back and forth between two bus stops, and the time taken for the trip in both directions is the same. Buses can be boarded at any time, and transfer times are negligible.

Both his home and the company are adjacent to bus stops, and he cannot walk to other bus stops or use any means of transportation other than buses.

Determine the place Takahashi should move to and output the maximum time he would have to spend on a bus after moving there.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ a_1 $ $ b_1 $ $ t_1 $ $ a_2 $ $ b_2 $ $ t_2 $ ： $ a_M $ $ b_M $ $ t_M $

• The first line contains two integers, $N\ (2\ ≦\ N\ ≦\ 300)$ representing the number of bus stops, and $M\ (N\ -\ 1\ ≦\ M\ ≦\ 44850)$ representing the number of routes, separated by a space.
• The following $ M $ lines contain information about the buses. The $ i $-th line contains integers $ a_i $, $b_i\ (1\ ≦\ a_i,\ b_i\ ≦\ N)$ representing the numbers of the two bus stops the bus travels between, and $t_i\ (1\ ≦\ t_i\ ≦\ 1000)$ representing the time in minutes it takes to travel that route, given as integers.
• It is guaranteed that there are no pairs of bus stops that cannot be reached from each other.
• It is guaranteed that $a_i\ ≠\ b_i$.
• There is at most one route that travels between any two bus stops.

Output Format

Output the maximum time Takahashi would have to spend on a bus after moving to the optimal location, on a single line. End the output with a newline.

Sample Input and Output

Sample Input #1

3 2
1 2 10
2 3 10

Sample Output #1

10

Sample Input #2

5 5
1 2 12
2 3 14
3 4 7
4 5 9
5 1 18

Sample Output #2

26

Sample Input #3

4 6
1 2 1
2 3 1
3 4 1
4 1 1
1 3 1
4 2 1

Sample Output #3

1

Notes/Hints

Sample Explanation 1

It takes 10 minutes to travel from bus stop 1 to bus stop 2. It takes 20 minutes to travel from bus stop 1 to bus stop 3. It takes 10 minutes to travel from bus stop 2 to bus stop 3. Therefore, moving to bus stop 2 results in the maximum ride time of 10 minutes, which is the best option.

Sample Explanation 2

Moving to bus stop 3 is the best option.

Sample Explanation 3

Note that even with multiple routes available, one should not take a detour.

见题面 Input 部分

见题面 Output 部分