더치페이

문제

$n$명의 친구들이 인덱스국에 여행을 떠난다. 인덱스국은 굉장히 넓고, 친구들은 각자 가보고 싶은 위치가 다르다. 따라 맨 처음에는 모두 1인 그룹으로 각자 여행을 하다가, 일정이 지나면서 그룹끼리 합류하여 마지막에는 하나의 그룹으로 뭉쳐서 다같이 여행을 마무리하기로 했다.

여행을 하는 데 지출은 필수적이다. 이 친구들은 각자 $2 \times 10^{18}$원씩을 가지고 있어서, 여행 동안에 돈을 그다지 계획적으로 쓰지는 않았다. 그래서 여행이 모두 끝난 후, 각자가 원래 부담했어야 할 몫을 정산하는 것이 무척 성가시게 되었다.

여행할 때 지출은 그룹 단위로 이루어지며, 여행할 때는 그룹원 중 한 명이 모두 계산한다. 여행이 모두 끝나고 정산할 때는 지출 당시의 모든 그룹원이 모두 공평하게 같은 금액만큼 부담한다. 금액은 원화로 계산하며, 각 지출은 당시 그룹원의 수로 나누어 떨어진다.

정산은 한 명이 다른 한 명에게 돈을 전송하는 송금을 통해 이루어진다. 매 지출마다 각자의 부담금을 계산하여 여행할 때 돈을 냈던 사람에게 송금을 하는 것은 매우 귀찮기 때문에, 친구들은 지출들을 모두 한꺼번에 정산해 $n$번 이하의 송금으로 모든 정산을 할 수 있는지 궁금해졌다.

그룹이 합류한 기록과 모든 지출의 기록이 시간 순서대로 주어진다. 여행이 모두 끝난 후, $n$번 이하의 송금으로 모든 지출을 정산할 수 없다면 -1, 정산할 수 있다면 송금 횟수와 송금에 대한 정보를 출력하도록 하자.

입력

입력의 첫 줄에 정수 $n, m$이 주어진다. $n$은 여행을 한 친구들의 수, $m$은 그룹의 합류 및 지출 기록의 총 개수이다. 각 친구들은 $1$번부터 $n$번까지의 번호로 표현한다.

이후 $m$개의 줄에 걸쳐 각 기록을 나타내는 수들이 한 줄에 하나씩 주어진다.

두 그룹이 합류한 기록은 1 x y와 같이 주어진다. 이는 x가 속한 그룹과 y가 속한 그룹이 합류했다는 것을 의미한다. x와 y가 이미 같은 그룹에 속해 있는 경우는 없다.

지출이 발생한 기록은 2 x c와 같이 주어진다. 이는 x가 현재 그룹원들을 위해 총 c원을 지출했다는 의미이다. c는 x가 속한 그룹의 그룹원의 수로 나누어 떨어진다.

기록들이 모두 처리된 시점에 모든 학생이 한 그룹에 속해 있음이 보장된다.

출력

첫째 줄에 조건을 만족하는 송금 방법이 존재하지 않으면 -1, 존재하면 송금의 총 횟수 $k$를 출력하라. (단, $0 \le k \le n$)

그 다음 $k$개 줄 각각에는 송금에 대한 정보를 조건에 맞게 출력하라. 여러 방법이 존재하면 그 중 아무거나 출력해도 좋고, 송금 또한 아무 순서로나 출력해도 괜찮다.

송금에 대한 정보는 x y c와 같이 나타내도록 하자. 이는 x가 y에게 c원을 보낸다는 의미이다. x와 y의 순서에 유의하라.

제한

• $1 \le n \le 100\,000$

• $n-1 \le m \le 200\,000$

• 각 지출에서의 지출 금액은 $10^{8}$을 넘지 않는 양의 정수이다.

• 각 송금에서의 송금 금액은 $2 \times 10^{13}$을 넘지 않는 양의 정수이어야 한다.

• 기록들이 모두 처리된 시점에 모든 학생이 한 그룹에 속해 있음이 보장된다.

3 5
1 2 3
2 1 7
2 3 42
1 2 1
2 1 30

3
2 3 21
2 1 10
3 1 10

출처

• 문제를 만든 사람: Diuven

• 문제를 검수한 사람: aeren, Green55, jhnah917, jhwest2, qwerasdfzxcl