Optimal Fast Food Delivery Restaurant Location

Little T plans to open a fast food delivery restaurant in City C. The delivery time to a certain location is proportional to the shortest distance between the restaurant and that location. Since the customers are spread out over the city's N buildings, Little T wants to choose a restaurant location that minimizes the maximum delivery distance (and hence the delivery time) for all customers.

The city has N buildings, connected by exactly N bidirectional roads. No two roads connect the same pair of buildings and any two buildings are reachable through a series of these roads. The restaurant may be established at any building or at any point along any road (the distances to the adjacent buildings need not be integers).

For any location p (which may lie on a road or coincide with a building), let \(d(p,v)\) denote the shortest distance from p to building v. The objective is to choose a location p such that the value \[ r = \max_{v \in V} d(p,v) \] is minimized. Output the minimized maximum distance.

Note: Roads are weighted, and the optimal location may lie anywhere along an edge.

inputFormat

The first line contains an integer N representing the number of buildings (and also the number of roads). Each of the next N lines contains three numbers u, v and w denoting a bidirectional road connecting building u and building v with length w. Buildings are numbered from 1 to N.

outputFormat

Output a single number, which is the minimized maximum distance from the optimal restaurant location to any building. Answers within an absolute or relative error of 1e-6 are accepted.

sample

3
1 2 2
2 3 2
3 1 3

2.000000