균형 예술

Pete Tencious는 모빌 작품으로 세계적으로 알려진 예술가이다. 샌프란시스코 현대미술관은 그의 작품 연작 Balance I, Balance II, Balance III, ...을 전시하고 있다. 각 작품에는 줄로 이어진 구가 둘 이상 있다. 줄의 양 끝에는 원반이 달려 있으며, 그 원반은 줄이 잇는 두 구에 붙어 있다. 각 구에 붙은 원반 수를 모두 더하면 구마다 같은 값이 나온다. Pete는 이 값을 모빌의 균형 수라고 부른다. 일부 줄에는 구 사이에 매달린 추가 원반도 있다. 작가는 이것이 인간의 간섭(구 사이의 추가 원반)에 훼손된 자연의 균형(구에 붙은 원반)을 나타낸다고 설명한다.

베이 지역에서 일어난 작은 지진으로 원반들이 떨어져 나와 이제 모두 구 사이에 느슨하게 매달려 있다. Pete는 Balance CCXLI를 작업 중이라 연락이 닿지 않으므로, 미술관 큐레이터들이 직접 모빌을 고쳐야 한다. 큐레이터들은 각 모빌의 원래 균형 수를 기억하지 못한다. 그래서 균형 수는 가능한 한 크게 하고, 구 사이에 남는 원반은 가능한 한 적게 하기로 했다. 그림 C.1은 첫 번째 예제에 해당하는 지진 후 모빌의 상태이다. 그림 C.2는 큐레이터가 원반을 옮겨 모든 구의 원반 수가 같아지고, 구 사이에 남는 원반이 최소가 되도록 한 방법의 예이다.

그림 C.1: 지진 후

그림 C.2: 균형 수를 최대로 만들기 위해 원반을 옮긴 상태

첫 줄에 양의 정수 $n$과 $m$이 주어진다. $n$ ($2 \leq n \leq 200$)은 구의 개수이며 구에는 1번부터 $n$번까지 번호가 붙어 있다. $m$ ($1 \leq m \leq 500$)은 줄의 개수이다. 이어지는 $m$개의 줄에는 정수 $s_1$, $s_2$, $d$가 주어진다. $s_1$과 $s_2$ ($1 \leq s_1, s_2 \leq n$, $s_1 \neq s_2$)는 그 줄이 잇는 두 구이고, $d$ ($0 \leq d \leq 10\,000$)는 지진 후 그 줄에 매달린 원반 수이다. 두 구 사이를 잇는 줄은 최대 하나이다.

균형 수를 최대로 만든 뒤, 구 사이의 줄에 매달려 남은 원반 수의 최솟값을 출력한다.