더치페이 정산

네덜란드 산간 지역으로 떠났던 휴가에서 막 돌아왔다. 여행 중에는 지출이 생길 때마다 나누어 내기가 번거로워서 영수증을 모두 모아 두었고, 누가 누구 몫으로 얼마를 냈는지 적어 두었다. 이제 정산할 차례다.

자기 몫을 대신 내 준 사람에게 각자 그대로 돌려주는 방법도 있다. 그러면 송금 횟수가 너무 많아지고, 여행에서 이어 온 게으름을 지키기 어렵다. 마지막에 모든 사람의 잔액이 $0$이 되기만 하면 누가 누구에게 보내는지는 상관없다.

정산을 끝내는 데 필요한 최소 송금 횟수를 구하라. 송금 한 번은 한 사람이 다른 한 사람에게 금액을 보내는 것이고, 모두가 원하는 만큼 보낼 현금 여유가 있다고 가정한다.

첫째 줄에 사람 수 $M$과 여행에서 모은 영수증 수 $N$이 주어진다. $1 \le M \le 20$, $0 \le N \le 1000$이다.

다음 $N$개 줄에 세 정수 $a$, $b$, $p$가 주어진다. $0 \le a, b < M$, $1 \le p \le 1000$이며, 사람 $a$가 사람 $b$ 몫으로 $p$ 유로를 냈다는 뜻이다.

모든 계산을 끝내는 데 필요한 최소 송금 횟수를 한 줄에 출력한다.