크루즈 퀘일

크루즈 퀘일은 마다가스카르의 아열대 숲(MST 숲) 땅에서 사는 신비로운 날지 못하는 새이다. 정해진 날짜에 같은 강을 오르내리는 연어처럼, 크루즈 퀘일도 날 수 없음에도 특정한 이동 패턴을 가진다. 이 패턴은 동물 탐색 연합(Union of Animal Finders) 과학자들의 주요 연구 주제이다.

수년에 걸쳐 이 과학자들은 크루즈 퀘일이 둥지를 틀 수 있는 둥지 구역 목록과, 둥지 구역을 연결하며 크루즈 퀘일이 걸어 다닐 수 있는 경로 목록을 밝혀냈다. 모든 크루즈 퀘일은 여름용 둥지 구역 하나와 겨울용 둥지 구역 하나를 가지며, 두 구역은 반드시 다르다. 해마다 이동할 때 각 크루즈 퀘일은 여름 둥지 구역에서 겨울 둥지 구역으로 경로를 따라 이동 경로를 지나 이동하며(도중에 다른 둥지 구역을 지날 수 있다), 그다음 겨울 둥지 구역에서 여름 둥지 구역으로 다른 이동 경로를 따라 돌아온다. 크루즈 퀘일은 여름 둥지 구역으로 돌아갈 때 항상 완전히 다른 경로를 택한다. 즉, 어떤 경로도 두 이동 경로에 함께 포함될 수 없다.

크루즈 퀘일에 대해 더 알아보기 위해 과학자들은 MST 숲의 일부 경로를 따라 카메라를 설치해 이들을 촬영하려 한다. 경로에 카메라가 설치되면, 크루즈 퀘일이 지나갈 때(방향에 관계없이) 카메라가 자동으로 작동한다. 그러나 경로에 카메라를 설치하는 일이 항상 쉬운 것은 아니며, 각 경로에는 카메라를 설치하는 데 드는 비용이 있다.

과학자들은 매년 모든 크루즈 퀘일의 사진을 찍으면서 카메라 설치에 드는 비용을 최소화하려 한다. 구체적으로, 크루즈 퀘일이 어떤 둥지 구역과 이동 경로를 따르든 모든 크루즈 퀘일이 두 이동 경로 중 적어도 하나에서 카메라가 설치된 경로를 적어도 하나 지나가도록 보장하고, 이를 보장하기 위한 카메라 설치 총비용의 최솟값을 알고자 한다.

그림 4: MST 숲 예시

예를 들어, 그림 4의 둥지 구역과 경로를 보자. 경로 옆의 정수는 그 경로에 카메라를 설치하는 비용이다. 크루즈 퀘일은 어느 경로든 어느 방향으로든 이동할 수 있다. 크루즈 퀘일이 이동할 수 있는 한 가지 경로는 (v1, v2, v5, v4, v1)일 수 있다. 이 특정 경로에 대해서는 v1에서 v4로 가는 경로에 카메라를 설치하는 것이 비용 최적해이다. 크루즈 퀘일이 택할 수 있는 모든 경로를 고려하면, 이 예시의 비용 최적해는 v1에서 v4로 가는 경로와 v3에서 v6으로 가는 경로에 카메라를 설치하는 것이며 총비용은 5(즉, 1 + 4)이다. 이렇게 하면 가능한 모든 이동 경로가 카메라가 설치된 경로를 적어도 하나 지나간다.

입력 파일은 여러 테스트 케이스로 이루어진다. 입력 파일의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 하나가 주어진다. 각 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 공백 하나로 구분된 두 정수 p와 r이 주어진다. 정수 3 ≤ p ≤ 2 000은 둥지 구역의 수이고, 정수 3 ≤ r ≤ 400 000은 경로의 수이다. 테스트 케이스의 나머지는 r개의 줄로 이루어진다. 1 ≤ i ≤ r에 대해 i번째 줄은 i번째 경로를 나타내며, 공백 하나로 구분된 세 정수 ui, vi, ci로 이루어진다. 1 ≤ ui ≤ p와 1 ≤ vi ≤ p는 i번째 경로가 연결하는 둥지 구역이고, 1 ≤ ci ≤ 3 000은 i번째 경로에 카메라를 설치하는 비용이다. 자기 자신으로 이어지는 경로는 없다. 즉, 모든 1 ≤ i ≤ r에 대해 xi ≠ yi이다. 또한 모든 경로는 서로 다르다. 즉, 1 ≤ i < j ≤ r인 모든 i, j에 대해 (ui, vi) ≠ (uj, vj)이고 (ui, vi) ≠ (vj, uj)이다.

입력의 각 테스트 케이스에 대해, 크루즈 퀘일이 이동하는 동안 카메라가 설치된 경로를 적어도 하나 지나가도록 MST 숲의 경로에 카메라를 설치하는 최소 총비용을 나타내는 정수 하나를 한 줄에 출력한다. 출력에는 빈 줄이 없어야 한다.