احزر ماذا؟ في عام 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$.