보안 시스템 설치

N개의 컴퓨터로 이루어진 네트워크가 있다. 일부 컴퓨터 쌍은 회선으로 직접 연결되어 있으며, 두 컴퓨터는 직접 연결된 회선을 이용하거나 다른 컴퓨터들을 거쳐 통신할 수 있다.

각 컴퓨터와 회선의 성능은 서로 다르므로, 직접 연결된 회선을 이용하는 데 걸리는 시간도 회선마다 다를 수 있다. 어떤 경우에는 직접 연결된 회선보다 다른 컴퓨터를 거치는 경로가 더 빠를 수도 있다. 여러 회선을 거쳐 통신하면 사용한 회선들의 통신 시간 합만큼 시간이 걸린다.

어느 날 해커가 네트워크에 침입하였다. 관리자는 모든 회선과 컴퓨터를 차단하여 공격을 막은 뒤, 보안 시스템을 한 대의 컴퓨터에만 설치하려고 한다. 어떤 컴퓨터가 공격받으면 그 사실이 네트워크를 통해 전달되고, 보안 시스템이 설치된 컴퓨터에서 보안 패킷을 전송한다. 준비가 끝난 뒤 네트워크를 복구할 때에는 다음 조건을 만족해야 한다.

1. 다시 공격받을 위험이 있으므로 가능한 한 적은 수의 회선만 복구한다. 단, 복구 후에는 서로 다른 두 컴퓨터 사이에 통신이 가능해야 한다.
2. 어느 컴퓨터가 공격받을지 알 수 없으므로, 보안 시스템이 설치된 컴퓨터에서 다른 모든 컴퓨터로 통신하는 데 필요한 평균 시간이 최소가 되도록 설치 위치를 정한다.

원래 네트워크의 정보가 주어졌을 때, 보안 시스템을 설치할 컴퓨터의 번호를 구하시오.

첫째 줄에 두 정수 N(1 <= N <= 200), M(1 <= M <= 10,000)이 주어진다.

다음 M개의 줄에는 회선 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C인 회선으로 연결되어 있음을 의미한다. 컴퓨터 번호는 1부터 N까지의 정수이다. C는 10,000 이하의 양의 정수이다.

모든 통신은 완전한 양방향으로 이루어지므로, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다.

첫째 줄에 보안 시스템을 설치할 컴퓨터의 번호를 출력한다.

답이 여러 개인 경우에는 번호가 가장 작은 컴퓨터를 출력한다.