이상하게도, 이 규칙은 자연스럽게 고려할 만한 규칙처럼 보이지만, 이전에 존재했던 예를 단 하나도 찾을 수 없다는 점은 나조차도 이상하게 느낍니다. 이따금 보이는 문제들이 조금 닮아 있기도 하지만, 그래도 완전히 같은 문제는 없습니다. 참 이상하군요. 또는 짝수일 수도요.

— Sam Cappleman-Lynes

정점이 $n$개이고 간선이 $m$개인 무방향 그래프가 주어집니다. $T$를 이 그래프의 스패닝 트리라고 하고, $\mathrm{Cost}(T)$를 $T$의 모든 간선 가중치의 합이라고 합시다. 다음 조건을 만족하는 $T_1$과 $T_2$를 구하세요.

• $\mathrm{Cost}(T_1)$은 짝수이며, $\mathrm{Cost}(T_1)$이 최소입니다.
• $\mathrm{Cost}(T_2)$는 홀수이며, $\mathrm{Cost}(T_2)$가 최소입니다.

입력

첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T \le 10^4$)가 하나 주어집니다. 각 테스트 케이스는 다음과 같습니다.

첫 번째 줄에는 정점 수와 간선 수를 나타내는 두 정수 $n$과 $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 5 \cdot 10^5$)이 주어집니다.

다음 $m$개의 줄에는 각각 무방향 간선 하나를 나타내는 세 정수 $u_i, v_i$, $w_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$, $1 \le w_i \le 10^9$)가 주어집니다.

모든 $n$의 합은 최대 $2 \cdot 10^5$이고, 모든 $m$의 합은 최대 $5 \cdot 10^5$임이 보장됩니다.

출력

각 테스트 케이스마다 $\mathrm{Cost}(T_1)$과 $\mathrm{Cost}(T_2)$ 두 정수를 한 줄에 출력하세요. 해당하는 스패닝 트리가 존재하지 않으면, 그 비용 대신 -1을 출력하세요.

예제

입력 1

3
2 1
1 2 5
3 1
1 3 1
4 4
1 2 1
1 3 1
1 4 1
2 4 2

출력 1

-1 5
-1 -1
4 3