황금의 산?

말레이시아의 르당산(Gunung Ledang)은 오래전부터 금이 많이 묻힌 산으로 전해졌고, 그리스와 중국에서까지 상인이 찾아왔다. 14세기에 믈라카 해협을 오가던 중국 뱃사람은 이 산을 킴 수아, 곧 황금의 산이라고 불렀다. 마자파힛 제국 시절에 붙은 이름 르당산은 멀리서 보이는 산이라는 뜻이다.

전설에 따르면 르당산의 공주는 세상이 처음 만들어지던 시절로 거슬러 올라가 엄청난 양의 금을 이 산에 숨겼다. 공주에게는 자신이 몸을 담근 웅덩이를 시간과 공간을 잇는 통로로 바꾸는 힘이 있었다. 한 역사학자가 세계 곳곳의 산 근처에서 그 웅덩이를 여럿 찾아내 르당 웅덩이라고 이름 붙였다.

르당 웅덩이에는 다음 성질이 있다.

• 웅덩이 하나는 서로 다른 두 산을 잇는 일방통행 통로다.
• 웅덩이를 지나는 데 드는 시간은 0이다.
• 한 산에 여러 웅덩이의 끝점이 있어도 된다.
• 르당산에서 출발하면 웅덩이를 차례로 갈아타서 어느 산에나 도착할 수 있다.
• 두 끝점이 같은 산에 있는 웅덩이는 없다.
• 웅덩이마다 두 끝점 사이의 시간 차가 정해져 있다. 예를 들어 어떤 웅덩이를 지나면 반대쪽 끝점에 42년 전 시점으로 도착한다.

지금 르당산에는 금이 없으므로 역사학자는 금이 과거의 르당산에 숨겨져 있다고 본다. 그는 현재의 르당산에서 출발해 웅덩이를 두 개 이상 지나 과거의 르당산으로 돌아오려 한다. 도착 시점이 현재보다 앞서기만 하면 몇 년 전인지는 상관없다. 이런 이동이 가능한지 판정하는 프로그램을 작성한다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 웅덩이 끝점이 있는 산의 수 $N$과 웅덩이의 수 $M$이 주어진다. 산에는 $0$번부터 $N-1$번까지 번호가 붙어 있고, $0$번이 말레이시아의 르당산이다.

다음 $M$개 줄에는 웅덩이 하나를 나타내는 세 정수 $A$, $B$, $C$가 주어진다. $A$번 산에서 이 웅덩이로 들어가면 $B$번 산의 $C$년 뒤 시점에 도착한다. $C$가 양수면 미래, 음수면 과거다.

각 테스트 케이스마다 Case #X: Y 형식으로 한 줄씩 출력한다. $X$는 1부터 세는 테스트 케이스 번호다. 과거의 르당산에 도착할 수 있으면 $Y$는 possible, 그렇지 않으면 not possible이다.

• $1 \le T \le 20$
• $1 \le N \le 1000$
• $0 \le M \le 2000$
• $0 \le A < N$, $0 \le B < N$, $A \ne B$
• $-1000 \le C \le 1000$
• $0$번 산에서 나머지 모든 산으로 가는 경로가 있다.
• 같은 두 산을 같은 방향으로 잇는 웅덩이가 여러 개 있을 수 있다.