### National Olympiad in Informatics, China, 2013

## Day 2, Problem 3 - Fast Food Restaurant

Little T is planning to open a delivery fast food restaurant in city C. The delivery time to a particular location is directly proportional to the length of the shortest path from the restaurant to the location. Little T would like to select a location for his restaurant so that the distance to the furthest customer is minimized.

Customers are located across the `N` establishments of city C. These `N` buildings just happen to be connected by `N` bidirectional roads. No two roads connect the same pair of buildings. For any pair of buildings, there exists at least one path connecting them made up of the bidirectional roads. Little T's restaurant can be built in any one of the buildings. Furthermore, it can also be built anywhere on any one of the bidirectional roads (the distances from the restaurant to the buildings on either ends of the road do not have to be integers).

Now, given a map of city C (road positions as well lengths), please determine the optimal site to build the restaurant, and output the furthest distance from any customer to this site.

### Input Format

The first line contains a single integer `N`, representing the number of buildings and roads in city C.

The next `N` lines will each contain 3 integers `A _{i}`,

`B`, and

_{i}`L`(1 ≤

_{i}`i`≤

`N`;

`L`> 0), indicating that a road of length

_{i}`L`exists between buildings

_{i}`A`and

_{i}`B`.

_{i}### Output Format

Output a single real number, rounded half-up to one digit after the decimal, the greatest distance from any customer to the restaurant if little T chooses the optimal location to build it.

### Sample Input 1

4 1 2 1 1 4 2 1 3 2 2 4 1

### Sample Output 1

2.0

### Explanation 1

As shown in the above diagram, the optimal site is on building 1. The distances to each of the buildings are respectively 0, 1, 2, and 2.

### Sample Input 2

5 1 5 100 2 1 77 3 2 80 4 1 64 5 3 41

### Sample Output 2

109.0

### Explanation 2

### Constraints

For 10% of the test cases: `N` ≤ 80 and `L _{i}` = 1;

For 30% of the test cases:

`N`≤ 600 and

`L`≤ 100;

_{i}For 60% of the test cases:

`N`≤ 2000 and

`L`≤ 10

_{i}^{9};

For 100% of the test cases:

`N`≤ 10

^{5}and

`L`≤ 10

_{i}^{9}.

All Submissions

Best Solutions

**Point Value:** 30 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 512M

**Added:** May 18, 2015

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...