Subway Replacement Optimization

You are given an undirected weighted graph representing intersections and roads. Each road connects two intersections with a given travel time. You are allowed to replace exactly one road with a subway route that has zero travel time. After this replacement, for every pair of intersections, the travel time is defined as the shortest path between them.

Your task is to determine the replacement that minimizes the maximum travel time between any two intersections. Mathematically, if \(d(i,j)\) represents the shortest travel time between intersections \(i\) and \(j\), you must compute:

\(\min_{\text{road replaced}} \; \max_{1\le i < j \le N} \; d(i,j)\)

You are given \(T\) test cases. For each test case, print the minimized maximum travel time after performing the optimal road replacement.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each test case is defined as follows:

• The first line of a test case contains two integers \(N\) and \(M\), where \(N\) is the number of intersections and \(M\) is the number of roads.
• This is followed by \(M\) lines, each containing three integers \(u\), \(v\), and \(w\) — representing a road between intersections \(u\) and \(v\) with travel time \(w\). The intersections are numbered from 1 to \(N\).

All input is provided via standard input (stdin).

outputFormat

For each test case, output a single integer on a new line representing the minimum possible value of the maximum travel time between any two intersections after replacing one road with a subway route. The result should be printed to standard output (stdout).

## sample

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

6
1

</p>