네트워크 복구

N(1 <= N <= 1,000)개의 컴퓨터로 이루어진 네트워크가 있다. 일부 컴퓨터 쌍은 회선으로 직접 연결되어 있고, 두 컴퓨터는 직접 연결된 회선이나 다른 컴퓨터를 거치는 경로를 통해 통신할 수 있다.

회선마다 통신 시간이 다르다. 직접 연결된 회선을 쓰면 그 회선의 통신 시간이 걸리고, 여러 회선을 거치면 각 회선 시간의 합이 걸린다. 직접 연결된 회선보다 다른 컴퓨터를 거치는 경로가 더 빠를 수도 있다.

침입 사고 뒤 관리자는 모든 컴퓨터와 회선을 차단했다. 보안 시스템은 버전 문제 때문에 1번 컴퓨터인 슈퍼컴퓨터 한 대에만 설치할 수 있다. 어떤 컴퓨터가 공격받으면 그 사실이 네트워크를 통해 슈퍼컴퓨터로 전달되고, 슈퍼컴퓨터는 네트워크를 통해 보안 패킷을 보낸다. 네트워크를 다시 복구할 때 다음 조건을 만족해야 한다.

1. 다시 공격받을 가능성이 있으므로 복구하는 회선 수를 최소화해야 한다. 단, 복구 후에는 서로 다른 두 컴퓨터 사이에 항상 통신할 수 있어야 한다.
2. 슈퍼컴퓨터에서 각 컴퓨터까지의 최단 통신 시간은 원래 네트워크에서의 최단 통신 시간보다 커지면 안 된다.

원래 네트워크 정보가 주어질 때 조건을 만족하는 복구 방법을 출력하라.

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선 정보 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간 C(1 <= C <= 10)인 회선으로 연결되어 있다는 뜻이다. 컴퓨터 번호는 1부터 N까지이며, 1번 컴퓨터가 보안 시스템을 설치할 슈퍼컴퓨터이다. 모든 회선은 양방향으로 통신할 수 있다.

첫째 줄에 복구할 회선의 개수 K를 출력한다. 다음 K개의 줄에는 복구할 회선을 나타내는 두 정수 A, B를 출력한다. 이는 A번 컴퓨터와 B번 컴퓨터를 연결하던 회선을 복구한다는 뜻이다. 출력 순서는 자유롭고, 가능한 답이 여러 개라면 그중 아무 것이나 하나를 출력하면 된다.