Simple Polygon

Let $S$ be a set of $n$ line segments. One endpoint of each segment lies on the x-axis, and the other lies above the x-axis. All endpoints are distinct, but segments may intersect at their interiors.

We want to draw a simple polygon $P$ such that every segment of $S$ is part of the boundary of $P$. That is, each segment is either an edge of $P$ or part of an edge. A polygon $P$ is simple if the angle at each vertex is not $180^\circ$, and no two edges meet except when two adjacent edges meet at a shared vertex.

Figure H.1 shows segment sets for which simple polygons can be drawn. The black solid segments belong to $S$. Adding the red dotted segments gives a simple polygon. The left figure has every endpoint of $S$ as a vertex of $P$. The right figure has a simple polygon with 6 vertices, where two endpoints each lie in the interior of an edge of $P$. An endpoint of $S$ does not have to be a vertex of $P$.

Figure H.1: Examples of line segments for which simple polygons can be drawn.

Figure H.2 shows segment sets for which no simple polygon can be drawn.

Figure H.2: Examples of line segments for which no simple polygon can be drawn.

If more than one simple polygon exists for a set, we want the one with the minimum boundary length. Figure H.3 shows a simple polygon whose boundary is shorter than that of any other simple polygon for its set.

Figure H.3: A simple polygon with the minimum boundary length.

Given a set of line segments, determine whether a simple polygon exists for the set. If it does, find a simple polygon with the minimum boundary length.

The first line contains an integer $n$ ($3 \le n \le 20{,}000$), the number of segments. Each of the next $n$ lines contains three integers $x_1$, $x_2$, and $y_2$ ($1 \le x_1, x_2, y_2 \le 10^6$). These describe the segment with endpoints $(x_1, 0)$ and $(x_2, y_2)$. All endpoints are distinct, so no two endpoints occupy the same position.

Print exactly one line. If a simple polygon exists, print the minimum boundary length rounded to one decimal place. Otherwise, print $-1$.