Optimal Palace Location

You are given a connected undirected weighted graph with n cities and m bidirectional roads. Each road connects two distinct cities and has a travel cost associated with it. Your task is to determine the optimal city for building a palace such that the maximum travel cost from the palace to any other city is minimized. In other words, for each candidate city, compute the shortest path distances to all other cities and take the maximum of these distances. The answer is the minimum value among these maximum distances.

Note: If there is only one city, the travel cost is 0.

The roads are provided as triples (u, v, w), meaning there is a road between city u and city v with cost w.

Mathematical Formulation:

For a given city i, let d(i, j) be the shortest distance from city i to city j. Define
\( M(i) = \max_{1 \le j \le n} d(i, j) \).
Your goal is to compute
\( \min_{1 \le i \le n} M(i) \).

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of cities.
• The second line contains an integer m (0 ≤ m ≤ 10⁵), the number of roads.
• Each of the next m lines contains three integers u, v, and w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 10⁹), representing a bidirectional road between cities u and v with travel cost w.

outputFormat

Output to standard output (stdout) a single integer — the minimum possible value for the maximum travel cost from the optimal palace location to any other city.

## sample

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

7

</p>