Where Ya Gonna Call?

Gooli is a large company that owns $B$ buildings in a hilly area. The buildings are numbered from 1 to $B$.

Last year, Gooli built a set of slides between the buildings. Slides are now the favorite way to travel between buildings. Suction technology makes every slide two-way, so a slide can be used in either direction. Some slides have turns, so their lengths do not always follow common sense. For example, they may break the triangle inequality. There is at most one slide between any pair of buildings.

Gooli wants to install a special super secure phone so the CEO can talk to other important people. The company wants to minimize the distance by slide from any building to the phone, so the CEO spends as little time as possible reaching it from any building. Gooli has no more carbon kilotubes to build new slides, and the CEO refuses any other transportation. The security team must find the best location that can be reached using only existing slides. The location may be a building or a point somewhere within a slide.

The CEO may take a slide, arrive at a building, then take another slide that starts there, and continue until she reaches the location. A slide used from end to end adds its full length to the distance. If she enters a slide and stops inside it to find the phone, only the used part adds to the distance. Only slide length counts. Walking within a building to connect to a new slide or to reach the phone counts as zero.

Find an optimal location for the phone and output the distance from it to a farthest building. The distance is the same for every optimal location.

The first line contains the number of test cases $T$. Each test case begins with a line containing the number of buildings $B$. Then $B-1$ lines follow. For $i = 2, 3, \ldots, B$, the $(i-1)$-th of these lines contains $D_{i1}, D_{i2}, \ldots, D_{i(i-1)}$. $D_{ij}$ is $-1$ if there is no slide between building $i$ and building $j$. Otherwise, $D_{ij}$ is the length of that slide.

For each test case, print one line Case #x: y. Here $x$ is the test case number starting from 1, and $y$ is the distance from an optimal phone location to a farthest building. Answers within an absolute or relative error of $10^{-6}$ are accepted.

• $1 \le T \le 100$.
• $2 \le B \le 50$.
• All buildings are reachable from any other building using only slides, possibly passing through intermediate buildings.
• $D_{ij} \ne 0$ for all $i, j$.

The last two cases would not appear in the Small dataset.

In Case #1, all buildings lie on a line. The only optimal location is the midpoint of that line, because any other point makes one of the end buildings farther away.

Case #2 is an equilateral triangle. Any of the three buildings is an optimal location.

Case #3 is also a triangle, but its sides have different lengths. Choosing any building leaves a farthest building at distance at least 3. Choosing a point inside the slide of length 3, at distance 0.5 from building 3, reduces the distance to a farthest building to 2.5.

In Case #4, the optimal location is inside the slide of length 10 between buildings 1 and 3, at distance 1.5 from building 3 and distance 8.5 from building 1.