Inicialmente, Snuke não consegue se mover de forma alguma. Há $n$ bilhetes, e o preço do $i$-ésimo bilhete é $p_i$. Se Snuke comprar o $i$-ésimo bilhete, para todos os pontos $(x, y)$ e um número não negativo $t$, ele poderá se mover de $(x, y)$ para $(x + ta_i, y + tb_i)$. Snuke quer comprar bilhetes e poder viajar entre quaisquer dois pontos. Calcule o menor preço total possível dos bilhetes que ele deve comprar.

Entrada

A primeira linha da entrada contém um inteiro $n$ ($1 \le n \le 2 \cdot 10^5$). Em seguida, há $n$ linhas; a $i$-ésima delas contém três inteiros $a_i$, $b_i$, $p_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le p_i \le 10^9$).

Saída

Imprima o menor preço total possível dos bilhetes que ele deve comprar para poder se mover entre quaisquer dois pontos. Se isso for impossível, imprima $-1$ em vez disso.

Exemplos

Entrada 1

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

Saída 1

4

Entrada 2

2
1 2 3
4 5 6

Saída 2

-1

Nota

No exemplo 1, é possível, por exemplo, comprar os bilhetes 1, 3, 6.