마라톤 훈련 방해하기

상근이와 선영이는 마라톤 대회에 참가하기 위해 훈련하고 있다. 오늘은 훈련용 경로를 정하려고 한다.

두 사람이 사는 나라에는 도시가 $N$개, 도로가 $M$개 있다. 모든 도로는 두 도시를 잇고 양방향으로 통행할 수 있다. 이 가운데 $N-1$개는 포장도로이고, 나머지는 비포장도로이다.

포장도로만 이용해도 어떤 도시에서 다른 어떤 도시로든 갈 수 있다. 즉, $N$개의 도시와 $N-1$개의 포장도로는 하나의 트리를 이룬다. 또한 한 도시에 연결된 도로는 최대 $10$개이다.

훈련 경로는 한 도시에서 출발해 여러 도로를 지난 뒤 출발한 도시로 되돌아오며 끝난다. 두 사람은 훈련 도중 아름다운 풍경도 즐기고 싶어서, 이미 지난 도시는 다시 지나지 않고 이미 지난 도로도 다시 지나지 않는다. 즉, 훈련 경로는 하나의 단순 사이클이다. 출발 도시는 어디여도 되고, 모든 도시를 방문할 필요는 없다.

뒤에서 달리는 사람은 앞사람이 바람을 막아 주어 더 편하게 달릴 수 있다. 그래서 두 사람은 도시에 들어설 때마다 앞뒤 자리를 맞바꾼다. 훈련량을 똑같이 맞추려면 지나는 도로의 수가 짝수여야 한다. 따라서 유효한 훈련 경로는 도로를 짝수 개 지나는 단순 사이클이다.

경쟁자인 상덕이와 희원이는 이런 훈련 경로가 하나도 생기지 않도록 비포장도로 일부를 폭파하기로 했다. 각 비포장도로를 폭파하는 비용(양수)은 입력으로 주어지며, 포장도로는 폭파할 수 없다.

도시와 도로가 주어졌을 때, 유효한 훈련 경로가 하나도 남지 않도록 만드는 데 필요한 최소 폭파 비용을 구하여라.

첫째 줄에 도시의 수 $N$과 도로의 수 $M$이 주어진다. ($2 \le N \le 1{,}000$, $N-1 \le M \le 5{,}000$)

다음 $M$개의 줄에 각각 세 정수 $A$, $B$, $C$가 주어진다. ($1 \le A, B \le N$, $0 \le C \le 10{,}000$) $A$와 $B$는 서로 다르며 그 도로가 잇는 두 도시를 뜻한다. $C = 0$이면 포장도로이고, $C > 0$이면 비포장도로이며 이때 $C$는 그 도로를 폭파하는 비용이다.

한 도시에 연결된 도로는 최대 $10$개이고, 두 도시를 잇는 도로는 많아야 하나이다.

유효한 훈련 경로가 하나도 남지 않도록 하는 데 필요한 최소 폭파 비용을 첫째 줄에 출력한다.

첫 번째 예제에서 훈련 조건을 만족하는 경로는 모두 다섯 가지이다. 비포장도로 $1$–$3$, $3$–$5$, $2$–$5$를 폭파하면 이 경로가 모두 사라지며, 이때 폭파 비용은 $2 + 2 + 1 = 5$이다. 도로 $2$–$4$와 $2$–$5$를 폭파해도 되지만 비용이 $5 + 1 = 6$으로 더 크다. 따라서 최소 비용은 $5$이다.