토성의 조직망

토성의 위성 엔켈라두스에서 온 잠입자가 인간 행세를 하며 지구 인구에 섞여 있다는 보고가 들어왔다.

누가 잠입자인지는 아직 밝혀내지 못했다. 다만 안드로이드 통신부는 가로챈 교신에서 두 가지를 확인했다. 잠입자는 주요 도시에 나뉘어 자리를 잡았고, 정확히 일곱 명이 한 조를 이루어 움직인다. 잠입자로 의심되는 사람에게는 각각 식별 번호를 붙여 두었다. 조와 조 사이에는 교신이 오가지 않는다.

가로챈 교신에는 각각 위협도가 매겨져 있다. 교신 기록에 드러난 연결 관계를 살펴서 인원이 정확히 일곱 명인 조를 모두 찾아라. 어떤 조의 위협도는 그 조 안에서 오간 교신의 위협도를 모두 더한 값이다.

교신으로 이어진 사람은 같은 조에 속한다. 두 사람이 직접 교신했거나 다른 사람을 거쳐 간접적으로 이어져 있으면 같은 조다. 어떤 교신에도 등장하지 않는 사람은 혼자서 한 조를 이룬다. 같은 두 사람 사이의 교신이 여러 번 기록될 수 있고, 기록된 줄마다 위협도를 따로 더한다.

입력은 테스트 케이스 하나로 이루어진다.

첫 줄에 사람 수 $n$ ($0 < n \le 200000$)과 처리할 교신 기록의 수 $m$ ($1 \le m \le 100000$)이 주어진다.

이어지는 $m$개의 줄에는 공백 하나로 구분된 정수 세 개가 주어진다. 차례대로 보낸 사람의 식별 번호 $id_s$, 받은 사람의 식별 번호 $id_r$ ($0 \le id_s, id_r < n$, $id_s \ne id_r$), 그 교신의 위협도 $t$ ($0 < t \le 10$)이다.

서로 교신이 확인된, 인원이 정확히 일곱 명인 조를 모두 출력한다.

조마다 한 줄을 쓴다. 그 조에 속한 사람 가운데 식별 번호가 가장 작은 사람의 번호를 쓰고, 공백 하나를 둔 다음 그 조의 위협도 합계를 쓴다.

위협도 합계가 큰 조부터 출력한다. 합계가 같은 조가 여럿이면 줄 앞에 쓴 식별 번호가 작은 조부터 출력한다.

인원이 정확히 일곱 명인 조가 하나도 없으면 다음 한 줄만 출력한다.

There is currently no threat to Earth