부동산 중개인

Rupert는 잉글랜드의 작은 마을에서 유일한 부동산 중개인으로 일하며 돈을 번다. 그가 파는 집마다 5%의 수수료를 요구한다.

Rupert는 1년에 한 번 큰 경매를 연다. 모든 가족(1번부터 n번까지)이 이 경매에 참여해야 하지만, 제안을 하거나 받아들이는 것은 선택 사항이다. 각자는 현재 집을 동시에 팔 수 있다는 조건 아래, 이사 가고 싶은 집에 입찰한다.

이 과정은 매우 투명해서, Rupert는 판매자를 대신해 올바른 구매자의 제안을 받아들이면 얼마의 수수료를 벌게 될지 정확히 알 수 있다. 그는 전체 수수료를 높이기 위해 일부 구매자의 제안을 버릴 수 있다. 실제로 특정 가족의 제안을 모두 버리고 그들이 현재 집에 그대로 살게 하는 편이 더 많은 돈을 벌어 준다면 그렇게 할 수도 있다.

제안을 최적으로 버릴 때 Rupert가 벌 수 있는 최대 수수료를 구하시오.

입력은 다음과 같다.

• 정수 n과 m이 있는 한 줄 (1 ≤ n ≤ 150, 0 ≤ m ≤ n × (n − 1)). n은 시장에 나온 가족 수이고 m은 제안 수이다.
• 제안을 설명하는 m개의 줄. i번째 줄에는 세 정수 fi, hi, ai가 있다 (1 ≤ fi, hi ≤ n, fi ≠ hi, 0 ≤ ai ≤ 10^6). 각각 제안을 하는 가족, 제안 대상 집을 소유한 가족, 제안 금액이다. 같은 가족이 같은 집에 두 개 이상의 제안을 하지 않는다.

제안을 최적으로 버릴 때 Rupert가 수수료로 벌게 될 금액을 출력하시오. 답은 절대 오차 또는 상대 오차 10^−6 이내여야 한다.