Изначально Snuke вообще не может двигаться. Есть $n$ билетов, и цена $i$-го билета равна $p_i$. Если Snuke купит $i$-й билет, то для всех точек $(x, y)$ и неотрицательного числа $t$ он сможет перемещаться из $(x, y)$ в $(x + ta_i, y + tb_i)$. Snuke хочет купить билеты так, чтобы иметь возможность путешествовать между любыми двумя точками. Вычислите минимально возможную суммарную цену билетов, которые ему необходимо купить.

Входные данные

Первая строка входных данных содержит одно целое число $n$ ($1 \le n \le 2 \cdot 10^5$). Затем следуют $n$ строк; $i$-я из них содержит три целых числа $a_i$, $b_i$, $p_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le p_i \le 10^9$).

Выходные данные

Выведите минимально возможную суммарную цену билетов, которые ему необходимо купить, чтобы перемещаться между любыми двумя точками. Если это невозможно, выведите $-1$.

Примеры

Входные данные 1

7
0 3 1
0 3 2
1 -1 2
0 0 1
-2 4 1
-4 0 1
2 1 2

Выходные данные 1

4

Входные данные 2

2
1 2 3
4 5 6

Выходные данные 2

-1

Примечание

В примере 1 можно, например, купить билеты 1, 3, 6.