ทายสิว่าอะไรเอ่ย? ในปี 6202 เซิร์ฟเวอร์ของ Little Cyan Fish กำลังต้อนรับสมาชิกคนที่ $10^6$ แล้ว! ไม่เคยได้ยินมาก่อนเหรอ? เซิร์ฟเวอร์นี้ หรือที่รู้จักกันในชื่อกลุ่มของ Qingyu เป็นที่ที่เพื่อน ๆ ของเขามาพบปะพูดคุยกันเรื่องการเขียนโปรแกรมเชิงแข่งขัน เรื่องที่ไม่ใช่การเขียนโปรแกรมเชิงแข่งขัน มุกตลกของ PKU อาหารในปักกิ่ง และแทบจะทุกเรื่องอื่น ๆ แต่ที่สำคัญที่สุด แชตนี้เต็มไปด้วยข้อความทุกวันว่าใครเป็นไอดอลของใคร

ตามธรรมเนียมแล้ว Little Cyan Fish กำลังจัดงานปาร์ตี้ไอดอลที่มีสมาชิก $n$ คน โดยแต่ละคนมีหมายเลขตั้งแต่ $1$ ถึง $n$ มีความสัมพันธ์ระหว่างแฟนคลับกับไอดอลทั้งหมด $m$ ความสัมพันธ์ในหมู่สมาชิกเหล่านี้: ในความสัมพันธ์ที่ $i$ สมาชิก $u_i$ เป็นแฟนคลับของสมาชิก $v_i$ และของขวัญจาก $u_i$ ที่มอบให้ $v_i$ มีราคา $w_i$ ในงานปาร์ตี้ สมาชิกแต่ละคนต้องมอบของขวัญพิเศษ เพียงชิ้นเดียวเท่านั้น ให้กับ หนึ่งในไอดอลของตน อย่างไรก็ตาม การที่สมาชิกสองคนแลกของขวัญซึ่งกันและกันคงจะน่ากระอักกระอ่วนใจ (แม้ว่าฟังดูจะโรแมนติกดีก็ตาม :p) ดังนั้นจึงห้ามไม่ให้สมาชิกคู่ใดมอบของขวัญให้กันและกัน

จงหาผลรวมราคาของขวัญที่น้อยที่สุด หรือระบุว่าไม่มีการจัดสรรที่ถูกต้องตามเงื่อนไข

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม $T$ ($1 \le T$) แทนจำนวนกรณีทดสอบ รายละเอียดของแต่ละกรณีทดสอบมีดังต่อไปนี้

บรรทัดแรกของแต่ละกรณีทดสอบประกอบด้วยจำนวนเต็มสองจำนวนคือ $n$ และ $m$ ($1 \le n \le 10^6$, $0 \le m \le 10^6$) แทนจำนวนสมาชิกและจำนวนความสัมพันธ์ระหว่างแฟนคลับกับไอดอลตามลำดับ

บรรทัดที่ $i$ จาก $m$ บรรทัดถัดมา ประกอบด้วยจำนวนเต็มสามจำนวนคือ $u_i$, $v_i$ และ $w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $0 \le w_i \le 10^9$) ซึ่งหมายความว่าสมาชิก $u_i$ เป็นแฟนคลับของสมาชิก $v_i$ และของขวัญจาก $u_i$ ที่มอบให้ $v_i$ มีราคา $w_i$

รับประกันว่าผลรวมของ $n$ จากทุกกรณีทดสอบไม่เกิน $10^6$ และผลรวมของ $m$ จากทุกกรณีทดสอบไม่เกิน $10^6$ รับประกันว่าคู่อันดับ $(u_i, v_i)$ แต่ละคู่จะปรากฏอย่างมากหนึ่งครั้งในหนึ่งกรณีทดสอบ สมาชิกสองคนอาจเป็นแฟนคลับของกันและกันได้

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้แสดงผลจำนวนเต็มหนึ่งจำนวน — ผลรวมราคาของขวัญที่น้อยที่สุดที่เป็นไปได้ หากไม่มีคำตอบ ให้แสดงผล $-1$ แสดงคำตอบแต่ละกรณีแยกบรรทัดกัน

ตัวอย่าง

ข้อมูลนำเข้า 1

3
3 3
1 2 1
2 3 2
3 1 3
2 2
1 2 0
2 1 0
3 4
1 2 0
1 3 1
2 1 0
3 2 0

ข้อมูลส่งออก 1

6
-1
1

หมายเหตุ

ในกรณีทดสอบที่หนึ่งของตัวอย่าง สมาชิก $1$ มอบของขวัญให้สมาชิก $2$ สมาชิก $2$ มอบให้สมาชิก $3$ และสมาชิก $3$ มอบให้สมาชิก $1$ ราคารวมคือ $1 + 2 + 3 = 6$

ในกรณีทดสอบที่สองของตัวอย่าง สมาชิก $1$ และ $2$ จะต้องมอบของขวัญให้กันและกัน ดังนั้นจึงไม่มีการจัดสรรที่ถูกต้องตามเงื่อนไข

ในกรณีทดสอบที่สามของตัวอย่าง สมาชิก $1$ มอบของขวัญให้สมาชิก $3$ สมาชิก $2$ มอบให้สมาชิก $1$ และสมาชิก $3$ มอบให้สมาชิก $2$ ราคารวมคือ $1$