I.O.U.

당신은 친구 모임에서 비용을 나누는 일을 간단하게 해 주는 새 앱을 개발하고 있다. 이 앱으로 친구들은 누가 비용을 냈는지, 그리고 그 비용을 다른 사람과 어떻게 나눠야 하는지를 I.O.U.(차용증)로 기록할 수 있다. 예를 들어 Alice가 Bob, Carol과 함께 먹은 식사비를 냈고 Bob의 몫이 $5, Carol의 몫이 $10이라면, Bob은 Alice에게 $5짜리 I.O.U.를, Carol은 Alice에게 $10짜리 I.O.U.를 발행한다.

앱은 누가 누구에게 얼마를 빚졌는지 장부로 관리한다. 순환이 생길 수도 있다. 예를 들어 Bob이 처음에 Alice에게 $10을 빚졌는데 나중에 Alice를 대신해 $5 비용을 냈다면, Alice는 Bob에게 $5짜리 I.O.U.를 발행한다. 이 I.O.U.는 Alice가 Bob에게서 받을 $10의 빚을 $5로 줄이며 일부를 상쇄한다. 순환에는 세 명 이상이 얽힐 수도 있다.

앱은 발행된 I.O.U. 목록을 받아, 가능한 한 모든 순환을 찾아 각 순환에서 가장 작은 빚 금액만큼 그 순환의 모든 빚을 줄여 정산한다. 모든 순환을 찾아 상쇄한 뒤, 앱은 누가 누구에게 얼마를 빚졌는지 출력한다. 상쇄하는 방법이 여러 가지라면 어느 것을 골라도 되지만, 마지막에 순환이 남아 있지 않아야 한다. 다만 서로 I.O.U.를 주고받은 적이 없는 친구 사이에 새 I.O.U.를 만들어서는 안 된다. 예를 들어 Alice가 Bob에게 돈을 빚지고 Bob이 같은 금액을 Carol에게 빚졌다고 해서, Bob을 빼고 Alice가 Carol에게 빚졌다고 선언할 수는 없다.

입력은 하나의 테스트 케이스로 이루어진다. 첫 줄에는 두 정수 $n$과 $m$ ($1 \le n \le 100$, $0 \le m \le 10\,000$)이 주어진다. $n$은 친구의 수이고 $m$은 발행된 I.O.U.의 수이다. 친구는 $0$부터 $n-1$까지 번호가 매겨져 있다. 이어서 $m$개의 줄에 각각 세 정수 $a$, $b$, $c$ ($0 \le a < n$, $0 \le b < n$, $a \ne b$, $0 < c \le 1\,000$)가 주어지며, 이는 친구 $a$가 친구 $b$에게 $c$달러짜리 I.O.U.를 준 것을 뜻한다. 어떤 친구 $i$가 다른 친구 $j$($i \ne j$)에게서 받는 I.O.U.는 최대 하나이지만, 친구 $j$가 $i$에게서 I.O.U.를 받는 동시에 친구 $i$가 $j$에게서 I.O.U.를 받는 것은 가능하다.

먼저 모든 순환을 상쇄한 뒤 남은 I.O.U.의 개수 $p$를 한 개의 수로 출력한다. 이어서 남은 $p$개의 I.O.U.를 입력과 같은 형식으로 다음 $p$개의 줄에 출력한다. 즉, 친구 $a$가 친구 $b$에게 $c$달러를 빚졌다는 뜻으로 세 정수 $a$, $b$, $c$를 출력한다. 완전히 상쇄된 I.O.U.는 출력하지 않는다. 출력하는 모든 I.O.U.의 $c$는 $0$보다 커야 한다.