Directions

각 표는 한 벡터 방향으로의 이동을 허용하므로, 벡터들이 평면 전체를 생성하도록 하는 최소 비용 부분집합을 고른다.

어려움8기하그래프최소 신장 트리아직 제출이 없습니다시간 제한4초메모리 제한512 MB

문제 설명

예제2

문제

Initially, Snuke can’t move at all. There are n tickets, and the price of the i-th ticket is pi. If Snuke buys the i-th ticket, for all points (x, y) and a nonnegative number t, he can move from (x, y) to (x + tai, y + tbi). Snuke wants to buy tickets and he wants to be able to travel between any two points. Compute the minimal possible total price of the tickets he must buy.

입력

First line of the input contains one integer n (1 ≤ n ≤ 2 · 105). Then n lines follow; i’th of these lines contains three integers ai, bi, pi (−109 ≤ ai, bi ≤ 109, 1 ≤ pi ≤ 109).

출력

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

힌트

In the Sample 1 you can, for example, buy tickets 1, 3, 6.