Indovina un po'? Nell'anno 6202, il server di Little Cyan Fish dà il benvenuto al suo $10^6$-esimo membro! Non ne hai mai sentito parlare? Beh, il server, noto anche come il gruppo di Qingyu, è il luogo in cui i suoi amici si ritrovano e parlano di programmazione competitiva, argomenti non legati alla programmazione competitiva, battute sulla PKU, cibo a Pechino e praticamente qualsiasi altra cosa. Ma soprattutto, la chat è piena ogni giorno di messaggi su chi sia l'idolo di chi.
Seguendo la tradizione, Little Cyan Fish sta organizzando una festa degli idoli con $n$ membri, numerati da $1$ a $n$. Ci sono $m$ relazioni fan–idolo tra questi membri: nella $i$-esima relazione, il membro $u_i$ è un fan del membro $v_i$, e un regalo da $u_i$ a $v_i$ costa $w_i$. Alla festa, ogni membro deve fare esattamente un regalo speciale a uno dei suoi idoli. Tuttavia, se due membri si scambiassero regali a vicenda sarebbe imbarazzante (anche se suona piuttosto dolce :p), quindi nessuna coppia di membri può farsi regali a vicenda.
Trova il costo totale minimo dei regali, oppure determina che non esiste alcuna disposizione valida.
Input
La prima riga contiene un intero $T$ ($1 \le T$), il numero di casi di test. Segue la descrizione dei casi di test.
La prima riga di ogni caso di test contiene due interi $n$ e $m$ ($1 \le n \le 10^6$, $0 \le m \le 10^6$), rispettivamente il numero di membri e il numero di relazioni fan–idolo.
La $i$-esima delle successive $m$ righe contiene tre interi $u_i$, $v_i$ e $w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $0 \le w_i \le 10^9$), dove il membro $u_i$ è un fan del membro $v_i$, e un regalo da $u_i$ a $v_i$ costa $w_i$.
È garantito che la somma di $n$ su tutti i casi di test non superi $10^6$, e la somma di $m$ su tutti i casi di test non superi $10^6$. È garantito che ogni coppia ordinata $(u_i, v_i)$ compaia al più una volta in un caso di test. Due membri possono essere fan l'uno dell'altro.
Output
Per ogni caso di test, stampa un intero — il minimo costo totale possibile dei regali. Se non esiste alcuna soluzione, stampa $-1$. Stampa ogni risposta su una riga separata.
Esempi
Input 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
Output 1
6 -1 1
Note
Nel primo caso di test di esempio, il membro $1$ fa un regalo al membro $2$, il membro $2$ al membro $3$ e il membro $3$ al membro $1$. Il costo totale è $1 + 2 + 3 = 6$.
Nel secondo caso di test di esempio, i membri $1$ e $2$ dovrebbero farsi regali a vicenda, quindi non esiste alcuna disposizione valida.
Nel terzo caso di test di esempio, il membro $1$ fa un regalo al membro $3$, il membro $2$ al membro $1$ e il membro $3$ al membro $2$. Il costo totale è $1$.