그거 아세요? 6202년, Little Cyan Fish의 서버가 $10^6$번째 멤버를 맞이했습니다! 한 번도 들어본 적 없으시다고요? Qingyu의 그룹이라고도 불리는 이 서버는 그의 친구들이 모여 경쟁 프로그래밍(CP), 비경쟁 프로그래밍, 베이징 대학(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$입니다.