Little T plans to open a fast-food delivery restaurant in City C. The time taken to deliver to a location is proportional to the shortest path distance from the restaurant to that location. Little T wants to choose a location for the restaurant such that the distance to the farthest customer is minimized.
The customers are distributed across $N$ buildings in City C. These $N$ buildings are connected by exactly $N$ bidirectional roads, and no two roads connect the same pair of buildings. There is at least one path consisting of bidirectional roads between any two buildings. Little T's restaurant can be opened in any building, or at any position along any road (the distance from this position to the buildings at the ends of the road does not have to be an integer).
Given the map of City C (road distribution and their lengths), find the optimal location for the fast-food restaurant and output the distance to the farthest customer.
Input
The first line contains an integer $N$, representing the number of buildings and roads in City C.
The next $N$ lines each contain 3 integers $A_i, B_i, L_i$ ($1 \le A_i, B_i \le N$; $L_i > 0$), indicating a road connects building $A_i$ and $B_i$ with length $L_i$.
Output
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 precision will not receive points.
Examples
Input 1
4 1 2 1 1 4 2 1 3 2 2 4 1
Output 1
2.0
Note 1
As shown in the figure, the optimal location is building 1. The distances to the 4 buildings are 0, 1, 2, 2.
Input 2
5 1 5 100 2 1 77 3 2 80 4 1 64 5 3 41
Output 2
109.0
Note 2
As shown in the figure.
Constraints
For 10% of the data, $N \le 80$, $L_i = 1$; For 30% of the data, $N \le 600$, $L_i \le 100$; For 60% of the data, $N \le 2000$, $L_i \le 10^9$; For 100% of the data, $N \le 10^5$, $L_i \le 10^9$.
Figure 1. Illustration of the optimal location for the restaurant in Example 1.