시간여행

문제 정보

문제

서기 4096년, 시공간을 넘어 은하계들을 서로 연결하는 웜홀들의 존재가 발견되었습니다. 웜홀은 빛의 속도로도 수백만 년이 걸릴 만큼 떨어져 있는 두 은하계 사이를 순식간에 이동할 수 있도록 해 줍니다. 그것보다 더 놀라운 것은 웜홀은 시간 여행을 가능하게 해 준다는 것입니다. 어떤 웜홀을 통과하면 과거로 가기도 하고, 어떤 웜홀을 통과하면 미래로 가기도 하지요.

인류의 개념과 지성의 보고 안드로메다 은하의 과거와 미래 모습을 조사하려고 합니다. 조사단은 현재의 지구에서 출발해, 웜홀들을 거쳐 과거나 미래의 안드로메다 은하로 갑니다. 조사단이 얼마나 과거로 갈 수 있는지, 그리고 얼마나 미래로 갈 수 있는지를 계산하는 프로그램을 작성하세요.

은하계들은 서로 너무 멀리 떨어져 있기 때문에, 웜홀을 통하지 않고 이동하는 것은 불가능합니다. 또한 조사단의 우주선에는 단거리 워프 기능이 있기 때문에, 같은 은하계 안에 있는 웜홀들 간을 이동하는 데는 시간이 걸리지 않습니다.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 인류에게 알려진 은하계의 수 V(2 <= V <= 100), 그리고 알려진 웜홀의 수 W(0 <= W <= 1000) 가 주어집니다. 각 은하계는 0번부터 V-1 번까지 번호가 매겨져 있으며, 지구가 위치하는 은하계는 0번, 안드로메다 은하계는 1번입니다.

그 후 W 줄에 각 3개의 정수 ai, bi, di (0 <= ai,bi < V, -1000 <= d <= 1000) 로 웜홀의 정보가 주어집니다. ai 와 bi 는 i 번 웜홀의 시작 은하계 번호와 종착 은하계 번호를 나타내며, 이 웜홀을 통과하면 현재 시간은 di 년만큼 변화하게 됩니다. di 가 양수면 미래로, di 가 음수면 과거로 가게 되지요.

모든 웜홀은 한 방향으로만 통과할 수 있습니다.

출력

각 테스트 케이스마다 한 줄을 출력합니다. 조사단이 웜홀을 통해 안드로메다 은하에 갈 방법이 없을 경우에는 UNREACHABLE을 출력합니다. 그 외의 경우, 안드로메다에 도착할 수 있는 가장 빠른 시간과 가장 늦은 시간이 현재와 몇 년 차이나는지 출력합니다. 무한히 과거로 갈 수 있는 경우나 무한히 미래로 갈 수 있는 경우 INFINITY를 대신 출력합니다. 자세한 것은 예제 입출력을 참조하세요.

예제 입력

4
2 2
0 1 1
0 1 3
4 4
0 2 -7
0 3 -4
3 2 9
2 1 3
4 3
0 2 0
2 2 1
2 1 0
3 0

예제 출력

1 3
-4 8
0 INFINITY
UNREACHABLE

노트

18개의 댓글이 있습니다.