마라톤 훈련 방해하기

상근이와 선영이는 보스턴 마라톤에 참가하기 위해 열심히 훈련하고 있다. 대회가 얼마 남지 않았기 때문에, 오늘은 훈련 계획을 세워보려고 한다.

두 사람이 살고있는 나라에는 도시가 N개, 도로가 M개 있다. 모든 도로는 두 도시를 연결하며, 양방향으로 이동할 수 있다. 도로 중에서 N-1개는 포장되어 있고, 나머지는 포장되어 있지 않다.

한 도시에서 다른 도시로 이동할 때, 항상 포장된 도로만을 사용해서 이동할 수 있다. 즉, N개의 도시와 N-1개의 포장된 도로는 트리 구조를 이루고 있다.

또, 한 도시와 연결되어 있는 도로는 최대 10개이다.

마라톤 훈련은 도시에서 시작해서, 도로를 돌아다닌 다음, 시작한 도시로 다시 돌아와서 끝난다. 상근이와 선영이는 훈련하면서 아름다운 풍경도 감상하려고 한다. 따라서, 그들은 이미 지나간 도시를 다시 지나가지 않을 것이고, 지난 도로도 다시 지나지 않을 것이다.

훈련을 시작 하는 도시는 어느곳이 되어도 상관없고, 모든 도시를 방문하지 않아도 된다.

뒤에서 달리는 것이 앞에서 달리는 것보다 더 편하다. 그 이유는 앞에서 달리는 사람이 바람을 막아주기 때문이다. 따라서, 상근이와 선영이는 도시에 들어갈 때 마다 자리를 서로 바꿀 것이다. 또, 서로 훈련한 양이 같아야 하기 때문에 짝수 개의 도로를 지나려고 한다.

상근이와 선영이의 경쟁자 상덕이와 희원이는 위의 조건을 만족시키는 경로를 없애기 위해 포장되어 있지 않은 도로의 일부를 폭파시키기로 했다. 각각의 포장되어 있지 않은 도로를 폭파시키는 비용은 입력으로 주어진다. (비용은 양수) 또, 포장된 도로는 폭파시킬 수 없다.

도시와 도로 네트워크가 주어졌을 때, 상근이와 선영이의 훈련 조건을 만족시키는 경로가 없게하기 위해서 필요한 폭파 비용의 최솟값을 구하는 프로그램을 작성하시오.

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

다음 M개 줄에는 A, B, C가 주어진다. (1 ≤ A, B ≤ N, 0 ≤ C ≤ 10,000) A와 B는 서로 다르며, 도로가 연결하는 도시를 나타낸다. C가 0인 경우는 포장된 도로이다. 포장되어 있지 않은 도로인 경우에는 C값이 양수이며, 이 값은 그 도로를 폭파시키는데 필요한 비용이다.

모든 도시는 많아야 10개 도로와 연결되어져 있다. 또, 한 도시 쌍을 연결하는 도로는 한 개를 넘지 않는다.

첫째 줄에 상근이와 선영이의 훈련 조건을 만족시키는 경로를 없애기 위한 폭파 비용의 최솟값을 출력한다.

위의 그림은 예제를 그래프로 나타낸 것이다. 굵은 도로는 포장된 도로이다.

상근이와 선영이의 훈련 조건을 만족 시키는 경로는 위와 같이 다섯 가지가 있다. 만약, 도로 1-3, 3-5, 2-5를 폭파시킨다면, 상근이와 선영이는 훈련을 할 수 없다. 이때, 총 폭파 비용은 5이다.

도로 2-4와 2-5를 폭파시켜도 된다. 하지만, 총 폭파 비용이 6이 된다.