Để mở đầu cho kỉ nguyên chinh phục vũ trụ, các nhà khoa học ở hành tinh Alpha đang tiến hành thiết kế một chiếc tàu vũ trụ. Trong đó, bộ phận quan trọng nhất là hệ thống động cơ của tàu.

Các nhà khoa học đã mô hình hóa vũ trụ thành hệ trục tọa độ Oxy trong không gian hai chiều, lấy hành tinh Alpha làm gốc tọa độ. Có ~n~ vị trí có thể lắp ráp động cơ trên tàu vũ trụ. Việc lắp ráp động cơ ở vị trí thứ ~i~ tốn chi phí là ~w_i~, và sẽ cho phép tàu di chuyển theo hướng ~(a_i, b_i)~. Cụ thể, giả sử tàu đang nằm ở tọa độ ~(x, y)~ thì khi sử dụng động cơ thứ ~i~ trong khoảng thời gian ~t~ (~t~ là số thực không âm, có thể lớn tùy ý) tàu sẽ đi đến vị trí ~(x + a_i \times t, y + b_i \times t)~.

Một trong những tiêu chí quan trọng nhất trong thiết kế hệ thống tên lửa là tàu phải đi đến được mọi địa điểm trong vũ trụ, tức là với mọi điểm ~(x, y)~, tàu luôn có thể xuất phát từ gốc tọa độ và đi đến điểm ~(x, y)~ chỉ bằng các động cơ được lắp ráp. Nói cách khác, giả sử tàu được lắp ráp động cơ ở các vị trí ~r_1, r_2, \dots, r_k~ thì cần đảm bảo rằng, với mọi điểm ~(x, y)~ luôn tồn tại một bộ số thực ~t_1, t_2, \dots, t_k~ không âm sao cho ~a_{r_1} \times t_1 + a_{r_2} \times t_2 + \dots + a_{r_k} \times t_k = x~ và ~b_{r_1} \times t_1 + b_{r_2} \times t_2 + \dots + b_{r_k} \times t_k = y~.

Hãy giúp các nhà khoa học hành tinh Alpha chọn ra các vị trí cần lắp ráp động cơ sao cho tàu có thể đi đến được mọi điểm trong vũ trụ, và tổng chi phí lắp ráp động cơ là nhỏ nhất.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ (~1 \le n \le 2 \times 10^5~) cho biết số vị trí có thể lắp động cơ.
• Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa ba số nguyên ~a_i, b_i, w_i~ (~|a_i|, |b_i| \le 10^9~, ~1 \le w_i \le 10^9~) cho biết hướng và chi phí lắp ráp động cơ ở vị trí thứ ~i~.

Output

• Ghi ra một số nguyên duy nhất là tổng chi phí nhỏ nhất để lắp ráp động cơ sao cho tàu có thể đi đến mọi điểm. Trong trường hợp không tồn tại các lắp ráp động cơ thỏa yêu cầu đề bài, hãy ghi ra ~-1~.

Sample Input 1

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

Sample Output 1

6

Sample Input 2

2
1 0 10
0 1 10

Sample Output 2

-1