Optimal Train Station Placement

You are given an undirected weighted graph with n intersections (numbered 1 to n) and m roads connecting them. Each road is bidirectional with a given travel time. In addition, you are allowed to add exactly one new connection (train station link) between any two distinct intersections with a travel time of 0.

After you add this new connection, the diameter of the graph is defined as the maximum shortest path distance between any pair of intersections. Your task is to choose a pair of intersections to connect by the new train line so that the resulting diameter is minimized.

More formally, let \(d(u,v)\) be the shortest distance between intersections \(u\) and \(v\) after adding the new 0 weight edge. The diameter of the graph is given by \(\max_{1 \le u < v \le n} d(u,v)\). You must compute the minimum possible diameter achievable by optimally choosing which pair of intersections to connect.

Note: If the graph is originally disconnected, the new connection helps to connect some components. However, there may remain disconnected components in certain cases. In this problem, you can assume that the input graphs are such that an optimal placement of the train connection will yield a finite diameter.

inputFormat

The first line contains two integers n and m (2 ≤ n, m, etc.) representing the number of intersections and roads respectively.

Each of the following m lines contains three integers \(u\), \(v\), and \(w\) (1 ≤ u, v ≤ n, w ≥ 1) indicating that there is a bidirectional road connecting intersection \(u\) and intersection \(v\) with travel time \(w\).

You must read input from standard input.

outputFormat

Output a single integer: the minimized diameter after optimally adding one new 0 weight connection. Write the answer to standard output.

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

8