CAPS 동아리원 명이 여러 차례 술자리를 가졌다. 각 술자리는 다음 규칙을 따른다.
모든 술자리가 끝난 뒤 동아리원들은 서로 돈을 주고받아 정산하려 한다. 반드시 대신 결제한 사람에게 직접 갚을 필요는 없으며, 최종적으로 각 사람이 실제 부담한 금액과 부담해야 할 금액이 같으면 된다.
정산 과정에서 사람들 사이에 송금되는 금액 총합의 최솟값을 구해 보자.
첫째 줄에 동아리원의 수 과 술자리의 수 이 주어진다. ()
각 술자리에 대해 두 줄이 주어진다. 첫째 줄에는 참석자 수 , 결제한 사람의 번호 , 총 결제 금액 가 주어진다. 둘째 줄에는 참석한 명의 번호가 주어진다.
, , 이다. 는 참석자이고, 참석자 번호는 서로 다르며, 는 의 배수이다. 모든 술자리의 의 합은 이하이다.
입력으로 주어지는 모든 수는 정수이다.
정산을 완료하기 위해 송금해야 하는 금액 총합의 최솟값을 출력한다.