ในตอนแรก Snuke ไม่สามารถเคลื่อนที่ได้เลย มีตั๋ว $n$ ใบ และราคาของตั๋วใบที่ $i$ คือ $p_i$ หาก Snuke ซื้อตั๋วใบที่ $i$ เขาจะสามารถเคลื่อนที่จาก $(x, y)$ ไปยัง $(x + ta_i, y + tb_i)$ ได้ สำหรับทุกจุด $(x, y)$ และจำนวนที่ไม่เป็นลบ $t$ 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 ได้ เป็นต้น