נחשו מה? בשנת 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$.