Problem Description

Little T plans to open a delivery fast food restaurant in city C. The time it takes to deliver to a location is proportional to the shortest path length between the restaurant and that location. Little T wants to choose a location for the restaurant that minimizes the distance to the farthest customer.

The customers of the fast food restaurant are distributed across \( N \) buildings in city C. These \( N \) buildings are connected by exactly \( N \) bidirectional roads, with no two roads connecting the same pair of buildings. There is at least one path connecting any two buildings via bidirectional roads. Little T's fast food restaurant can be located in any building or at any point on any road (the distance from this point to the buildings at both ends of the road does not have to be an integer).

Given the map of city C (the distribution and lengths of the roads), find the optimal location for the fast food restaurant and output the distance to the farthest customer.

Input Format

The first line contains an integer \( N \), representing the number of buildings and roads in city C.

The next \( N \) lines each contain three integers \( A_i, B_i, L_i \) (\( 1 \leq i \leq N \), \( L_i > 0 \)), indicating that there is a road connecting building \( A_i \) and building \( B_i \) with a length of \( L_i \).

Output Format

Output a single real number, rounded to exactly one decimal place, representing the distance from the optimal restaurant location to the farthest customer.

Note: Your result must have exactly one decimal place; incorrect decimal places will result in no points.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2.0

Sample Input #2

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

Sample Output #2

109.0

Notes

Sample Explanation 1

(Image link provided in original problem)

Sample Explanation 2

(Image link provided in original problem)

Data Range

• For \( 10\% \) of the data, \( N \leq 80 \), \( L_i = 1 \);
• For \( 30\% \) of the data, \( N \leq 600 \), \( L_i \leq 100 \);
• For \( 60\% \) of the data, \( N \leq 2000 \), \( L_i \leq 10^9 \);
• For \( 100\% \) of the data, \( 1 \leq N \leq 10^5 \), \( 1 \leq L_i \leq 10^9 \).

见题面 Input 部分

见题面 Output 部分