Directions

Time limit4sMemory limit512 MB

Summary

Pick the cheapest set of direction vectors whose nonnegative multiples let Snuke reach any point from any other, or print -1 if no set works.

Level: Hard8 of 10
Topics: Geometry, Sorting, Dynamic programming
Solved: No attempts yet

Problem

Initially, Snuke cannot move at all. There are $n$ tickets, and the price of the $i$ -th ticket is $p_i$ . If Snuke buys the $i$ -th ticket, then for every point $(x, y)$ and every nonnegative number $t$ , he can move from $(x, y)$ to $(x + t a_i, y + t b_i)$ . Snuke wants to buy tickets so that he can travel between any two points. Compute the minimal possible total price of the tickets he must buy.

Input

The first line contains one integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ). Then $n$ lines follow, the $i$ -th of which contains three integers $a_i$ , $b_i$ , $p_i$ ( $-10^9 \le a_i, b_i \le 10^9$ , $1 \le p_i \le 10^9$ ).

Output

Print the minimal possible total price of the tickets he must buy to be able to move between any two points. If this is impossible, print -1 instead.

Hint

For example, Snuke can buy tickets 1, 3, and 6.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
2
1 2 3
4 5 6
```
Expected output
```
-1
```