Tebak apa? Pada tahun 6202, server Little Cyan Fish menyambut anggotanya yang ke-$10^6$! Belum pernah mendengarnya? Nah, server tersebut, yang juga dikenal sebagai grup Qingyu, adalah tempat teman-temannya berkumpul dan mengobrol tentang CP, non-CP, lelucon PKU, makanan di Beijing, dan hampir segala hal lainnya. Namun yang paling penting, obrolan di sana setiap hari dipenuhi pesan tentang siapa yang menjadi idola siapa.

Mengikuti tradisi, Little Cyan Fish mengadakan pesta idola dengan $n$ anggota, yang dinomori dari $1$ hingga $n$. Terdapat $m$ hubungan penggemar–idola di antara para anggota ini: pada hubungan ke-$i$, anggota $u_i$ adalah penggemar dari anggota $v_i$, dan sebuah hadiah dari $u_i$ kepada $v_i$ membutuhkan biaya $w_i$. Di pesta tersebut, setiap anggota harus memberikan tepat satu hadiah spesial kepada salah satu idolanya. Akan tetapi, dua anggota yang saling bertukar hadiah satu sama lain akan terasa canggung (walaupun terdengar cukup manis :p), sehingga tidak boleh ada pasangan anggota yang saling memberikan hadiah satu sama lain.

Carilah total biaya minimum dari hadiah-hadiah tersebut, atau tentukan bahwa tidak ada pengaturan yang valid.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T$), yaitu banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul di bawahnya.

Baris pertama dari setiap kasus uji berisi dua bilangan bulat $n$ dan $m$ ($1 \le n \le 10^6$, $0 \le m \le 10^6$), masing-masing menyatakan banyaknya anggota dan banyaknya hubungan penggemar–idola.

Baris ke-$i$ dari $m$ baris berikutnya berisi tiga bilangan bulat $u_i$, $v_i$, dan $w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $0 \le w_i \le 10^9$), di mana anggota $u_i$ adalah penggemar dari anggota $v_i$, dan sebuah hadiah dari $u_i$ kepada $v_i$ membutuhkan biaya $w_i$.

Dijamin bahwa jumlah nilai $n$ di seluruh kasus uji tidak melebihi $10^6$, dan jumlah nilai $m$ di seluruh kasus uji tidak melebihi $10^6$. Dijamin pula bahwa setiap pasangan terurut $(u_i, v_i)$ muncul paling banyak satu kali dalam satu kasus uji. Dua anggota dapat saling menjadi penggemar satu sama lain.

Keluaran

Untuk setiap kasus uji, keluarkan sebuah bilangan bulat — total biaya hadiah minimum yang mungkin. Jika tidak ada solusi, keluarkan $-1$. Keluarkan setiap jawaban pada baris terpisah.

Contoh

Masukan 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

Keluaran 1

6
-1
1

Catatan

Pada kasus uji contoh pertama, anggota $1$ memberikan hadiah kepada anggota $2$, anggota $2$ kepada anggota $3$, dan anggota $3$ kepada anggota $1$. Total biayanya adalah $1 + 2 + 3 = 6$.

Pada kasus uji contoh kedua, anggota $1$ dan $2$ harus saling memberikan hadiah satu sama lain, sehingga tidak ada pengaturan yang valid.

Pada kasus uji contoh ketiga, anggota $1$ memberikan hadiah kepada anggota $3$, anggota $2$ kepada anggota $1$, dan anggota $3$ kepada anggota $2$. Total biayanya adalah $1$.