Вгадайте що? У 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$. Виводьте кожну відповідь в окремому рядку.

Приклади

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

У першому тестовому прикладі учасник $1$ дарує подарунок учаснику $2$, учасник $2$ — учаснику $3$, а учасник $3$ — учаснику $1$. Загальна вартість дорівнює $1 + 2 + 3 = 6$.

У другому тестовому прикладі учасникам $1$ і $2$ довелося б подарувати подарунки одне одному, тому допустимого способу не існує.

У третьому тестовому прикладі учасник $1$ дарує подарунок учаснику $3$, учасник $2$ — учаснику $1$, а учасник $3$ — учаснику $2$. Загальна вартість дорівнює $1$.