비크포드 도화선

맑은 날 고슴도치가 좋아하는 풀밭을 거닐다가 전에는 없던 이상한 물건을 발견했다. 멀리서 보면 엉킨 줄 뭉치처럼 보였다. 가까이 가서 줄을 풀고 재료를 살펴본 고슴도치는 이것이 비크포드 도화선이라고 결론 내렸다.

자세히 보니 이걸 만든 사람은 심심했고 시간이 많았던 것이 분명했다. 도화선이 엉켜 있었고 매듭도 아주 많았다. 꼼꼼히 세어 보니 매듭은 모두 $n$개였고, 매듭 사이를 잇는 연결은 $m$개였다. 각 연결은 두 매듭을 잇고 일정한 속도로 탄다. 어떤 매듭에 불이 붙으면, 그 매듭을 포함한 모든 연결에 불이 붙는다.

고슴도치는 이 물건이 마음에 들지 않아 없애기로 했다. 주머니에 마침 챙겨 둔 성냥이 있었다. 성냥으로 매듭 하나에 불을 붙일 수 있고, 그러면 전체 구조가 타기 시작한다. 고슴도치는 바쁜 몸이라 이 구조가 가능한 한 빨리 다 타기를 바란다. 어느 매듭에 불을 붙여야 하는지 알려 달라.

첫 줄에 매듭의 개수 $n$과 매듭 사이를 잇는 줄의 개수 $m$이 주어진다 ($2 \le n \le 100$, $1 \le m \le \frac{n \cdot (n - 1)}{2}$).

다음 $m$개의 줄에는 정수 $a_i$, $b_i$, $t_i$가 주어진다 ($1 \le a_i, b_i \le n$, $a_i \neq b_i$, $1 \le t_i \le 1000$). 이는 $i$번째 줄이 잇는 두 매듭의 번호와, 한쪽 끝에서 불을 붙였을 때 그 줄이 완전히 타는 데 걸리는 초 단위 시간이다.

두 매듭을 잇는 줄은 최대 하나뿐이다. 어느 매듭에 불을 붙이든 도화선 전체가 다 탈 수 있음이 보장된다.

불을 붙일 매듭의 번호와, 그 매듭에 불을 붙였을 때 도화선 전체가 다 타는 데 걸리는 시간을 한 쌍의 수로 출력한다.