Угадайте что? В 6202 году сервер Маленькой Голубой Рыбки (Little Cyan Fish) встречает своего $10^6$-го участника! Никогда о нём не слышали? Что ж, этот сервер, также известный как группа Qingyu — место, где его друзья общаются и обсуждают спортивное программирование, неспортивное программирование, шутки про Пекинский университет (PKU), еду в Пекине и вообще всё на свете. Но самое главное — чат каждый день полон сообщений о том, кто чей кумир.

Следуя традиции, Маленькая Голубая Рыбка организует вечеринку кумиров с $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$.