Taco: Minimum Maximum Travel Time

You are given an undirected weighted graph representing the kingdom's cities and roads. There are N cities numbered from 1 to N. Each road connects two different cities and has an associated travel time. Your task is to find a city such that when chosen as the center, the maximum travel time required to reach any other city is minimized. In other words, if you choose a city as the central hub and calculate the shortest travel times to all other cities, you want the maximum of these times to be as small as possible.

Formally, let \(d(u,v)\) represent the shortest travel time between cities \(u\) and \(v\). For a chosen city \(c\), define \(T(c)=\max_{v}\{d(c,v)\}.\) Your goal is to minimize \(T(c)\) over all choices of \(c\). Output the minimized maximum travel time.

Note: If the graph is not fully connected, assume that all cities are reachable from one another.

inputFormat

The input is given via standard input (stdin) as space-separated integers. The first integer is N (the number of cities). The remaining integers represent the roads. Each road is described by three consecutive integers: u, v, and w, where u and v are the cities connected by the road and w is the travel time between them.

There is no explicit count of the number of roads; you can determine this as \(M = \frac{\text{total integers} - 1}{3}\).

outputFormat

Output a single integer to standard output (stdout) which is the minimum possible maximum travel time from the optimally selected city to all other cities.

4 1 2 4 2 3 2 2 4 3

4