Не болғанын білесіз бе? 6202 жылы Little Cyan Fish сервері өзінің $10^6$-шы қатысушысын қарсы алуда! Ол туралы естімегенсіз бе? Жалпы, Qingyu тобы деп те аталатын бұл сервер — оның достары жиналып, спорттық бағдарламалау, спорттық бағдарламалаудан тыс тақырыптар, PKU әзілдері, Бейжіңдегі тағамдар және басқа да кез келген нәрсе туралы әңгімелесетін орын. Бірақ ең бастысы — чатта күн сайын кімнің кімге кумир екені туралы хабарламалар толып тұрады.
Дәстүр бойынша, Little Cyan Fish $1$-ден $n$-ге дейін нөмірленген $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$) — сәйкесінше қатысушылар саны мен жанкүйер–кумир қарым-қатынастарының саны берілген.
Келесі $m$ жолдың $i$-ші жолында үш бүтін сан $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$ тең.