초대장

텔레비전의 시대가 되면서 연극 공연을 보러 오는 사람이 그리 많지 않습니다. 말리디네시아의 앤티크 코미디언들(Antique Comedians of Malidinesia)은 이 사실을 잘 알고 있습니다. 그들은 연극, 그중에서도 특히 앤티크 코미디를 널리 알리고 싶어 합니다. 그래서 필요한 모든 정보와 공연 프로그램을 담은 초대장을 인쇄하고, 이 초대장을 사람들에게 나누어 줄 많은 학생 자원봉사자를 모집했습니다. 각 학생 자원봉사자에게는 정확히 하나의 버스 정류장이 배정되며, 그 학생은 하루 종일 그 정류장에 머무르면서 버스를 이용하는 사람들에게 초대장을 나누어 줍니다.

이 도시의 교통 체계는 매우 특이합니다. 모든 노선은 단방향이며, 정확히 두 정류장만을 연결합니다. 버스는 출발 정류장에서 30분마다 승객을 태우고 떠나고, 도착 정류장에 이르면 빈 차로 출발 정류장까지 되돌아와 다음 출발 시각까지 기다립니다. 두 정류장 사이의 요금은 정해져 있으며, 탈 때 그 자리에서 지불합니다. 노선은 어느 정류장에서 출발해 같은 정류장으로 돌아오는 모든 왕복 여정이 반드시 중앙 검문 정류장(Central Checkpoint Stop, CCS)을 지나도록 설계되어 있습니다.

모든 자원봉사자는 매일 아침 CCS에서 출발합니다. 각 자원봉사자는 미리 정해진 하나의 정류장으로 이동하여 그곳에서 초대장을 나누어 줍니다. 자원봉사자의 수는 정류장의 수와 같으며, 정류장마다 한 명씩 배정됩니다. 하루가 끝나면 모든 자원봉사자는 다시 CCS로 돌아옵니다. 모든 자원봉사자의 하루 교통비 합계를 최소로 만드는 프로그램을 작성하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 양의 정수 N이 주어집니다. 그다음에 N개의 테스트 케이스가 이어집니다.

각 테스트 케이스의 첫 줄에는 두 정수 P와 Q가 주어집니다 (1 <= P, Q <= 1000000). P는 CCS를 포함한 정류장의 수이고, Q는 버스 노선의 수입니다. 이어서 Q개의 줄이 주어지며, 각 줄은 하나의 버스 노선을 나타냅니다. 각 줄에는 세 개의 정수, 즉 출발 정류장, 도착 정류장, 그리고 요금이 주어집니다. CCS는 번호 1로 지정됩니다. 요금은 모두 양의 정수이며, 모든 요금의 합은 1000000000보다 작습니다. 또한 어떤 정류장에서든 다른 모든 정류장으로 항상 이동할 수 있다고 가정할 수 있습니다.

각 테스트 케이스마다, 모든 자원봉사자의 이동을 위해 하루에 지불해야 하는 최소 금액을 한 줄에 출력하세요.