该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Background

In a game of Bed Wars, Muxue's bed was destroyed by enemies right at the start. His teammates quit the game, leaving only Muxue alone. Although Muxue is at a disadvantage in this round, he is a strong player and will not surrender.

The courage to turn the tide in a desperate situation is the true reflection of your dignity.

"Just as in building a mound, if I stop one basket short, the stopping is my own doing. Just as in leveling the ground, even if I have only dumped one basket of soil, the advancing is my own doing."

Problem Description

Muxue keenly observes that there are now $n$ enemy teams whose beds have not yet been destroyed. The bed of the $i$-th team is located at $(x_i, y_i)$, and Muxue's hatred value toward this team is $c_i$.

Design a bed-destroying route that starts at $(0,0)$ and destroys all beds in non-increasing order of hatred value, such that the total distance traveled is minimized. Note that you may pass by a bed without destroying it, and this does not violate the "non-increasing hatred value" constraint.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain three integers: $x_i, y_i, c_i$.

Output Format

Output a single real number — the shortest distance, rounded to two decimal places.

Sample Input/Output 1

Input

5
2 3 4
2 2 4
1 1 12
-1 1 12
1 2 8

Output

6.41

Data Scale and Constraints

Let $m$ be the maximum number of teams with the same $c_i$ in a test case.

Subtask 1 (10 points): $m = 1$

Subtask 2 (10 points): $n = m$, $m \le 7$

Subtask 3 (20 points): $n = m$

Subtask 4 (20 points): $m \le 7$

Subtask 5 (40 points): No additional constraints

For all data:$1 \le n \le 100$, $1 \le m \le 12$, $-1000 \le x_i, y_i \le 1000$, $1 \le c_i \le 10^9$.