폭주하는 타임머신

시간여행 외판원 Tim은 시공간의 여러 지점을 오가는 데 쓰는 타임머신 여러 대를 가지고 있다. 타임머신은 웜홀 네트워크를 따라 이동하는데, 각 웜홀은 시공간의 두 지점을 잇고 통과하는 데 정해진 시간이 걸린다. Tim의 타임머신은 완전 자동이라 목적지까지 항상 최단 경로로 이동한다.

최근의 격렬한 웜홀 폭풍으로 일부 타임머신이 폭주했다. 폭주한 각 타임머신은 메모리에 저장된 하나의 목적지를 불러와 출발했다. 이동을 마친 타임머신은 출발 지점과 이동에 걸린 총 시간을 담은 진단 신호를 송출했다. Tim은 각 타임머신에 어떤 목적지가 프로그램되어 있었는지 기억하지 못하지만, 어떤 두 타임머신도 같은 목적지로 프로그램되지 않았다는 사실은 알고 있다.

각 타임머신에 대해 출발 지점과 총 이동 시간이 주어진다. 타임머신의 목적지는 출발 지점으로부터의 최단 거리가 그 이동 시간과 같은 지점이다. 모든 타임머신의 목적지를 유일하게 결정할 수 있는지 판단하라.

첫 줄에는 데이터 집합의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 세 정수 $M$, $N$, $W$가 주어진다 ($1 \le M \le 20$, $2 \le N \le 100$, $N - 1 \le W \le 500$). 여기서 $M$은 사라진 타임머신의 수, $N$은 시공간 지점의 수, $W$는 웜홀의 수이다. 타임머신은 $1$번부터 $M$번까지, 지점은 $1$번부터 $N$번까지 번호가 매겨진다.

이어지는 $W$개의 줄에는 각각 세 정수 $a_i$, $b_i$, $c_i$가 주어진다. 웜홀 $i$는 지점 $a_i$와 $b_i$를 잇고, 양방향 어느 쪽으로든 통과하는 데 $c_i$초가 걸린다. 통과에 1,000초를 넘는 웜홀은 없다.

마지막 $M$개의 줄에는 각각 두 정수 $s_i$와 $t_i$가 주어진다. 이는 타임머신 $i$의 출발 지점과 총 이동 시간(초)이다. 모든 타임머신은 어떤 목적지까지 올바른 최단 경로를 따라 이동했음이 보장되며, 어떤 두 타임머신도 목적지가 같지 않다.

각 데이터 집합에 대해, 먼저 "Data Set x:"를 한 줄에 출력한다. 여기서 $x$는 데이터 집합의 번호이다(1부터 시작).

모든 타임머신의 목적지를 유일하게 결정할 수 있으면, 타임머신 $1$번부터 $M$번까지의 도착 지점을 한 줄에 공백 하나로 구분하여 출력한다. 줄의 앞뒤에 불필요한 공백이 있어서는 안 된다. 하나 이상의 타임머신의 목적지를 유일하게 결정할 수 없으면 대신 "impossible"을 출력한다.

이어지는 데이터 집합 사이에는 빈 줄 하나를 넣어 구분한다.