진한

고조선이 무너진 뒤, 고구려·백제·신라가 아직 온전한 국가로 성장하기 전까지의 시기를 삼한 시대(원삼국 시대)라고 부른다. 이 시기 한반도 중부와 남부의 여러 소국(도시국가)은 마한, 진한, 변한이라는 세 연맹체로 묶여 있었다. '삼(三)'은 셋을 뜻하고 '한(韓)'은 '크다' 또는 '우두머리'를 뜻하는 옛말에서 왔으며, 이 이름들은 오늘날 국호인 '대한민국'에도 남아 있다.

기원전 57년 박혁거세가 지금의 경주 부근에 세운 사로국은 진한 연맹을 이끄는 소국이었다. 사로국은 세력을 넓히며 이름을 신라로 바꾸었고, 신라는 아시아 역사에서 가장 오래 이어진 왕조가 되었다. 사로국을 제외한 진한의 다른 소국들에 대해서는 이름 정도만 전해질 뿐 알려진 바가 거의 없었다.

최근 저명한 고고학자 최 교수가 박혁거세의 무덤을 발견했다고 발표했다. 이 발굴 덕분에 진한 사람들의 생활상을 조금이나마 알 수 있게 되었지만, 사로국을 제외한 소국들의 위치는 여전히 밝혀지지 않았다. 최 교수가 무덤 석벽에 새겨진 비문을 해독한 결과, 일부 소국 쌍 사이의 거리가 알려지게 되었으며, 여기에는 사로국과 다른 모든 소국 사이의 거리도 포함된다.

최 교수는 진한이 태백산맥과 동해 사이에 자리했다는 점에 근거해, 소국들이 한 줄로 늘어서 있었다고 추측한다. 이를 검증하기 위해 그는 다음과 같은 수학 모형을 세웠다. 진한이 차지한 영역을 하나의 직선, 곧 x축으로 단순화하고, 각 소국의 위치를 x축 위의 한 점으로 나타낸다. 두 소국 사이의 거리는 두 위치의 차의 절댓값과 같은 양의 정수이며, 사로국은 x축의 원점에 놓인다고 가정한다.

소국에는 $1$번부터 $n$번까지 번호를 매기며, 사로국의 번호는 $1$번이다. 어떤 두 소국도 같은 지점에 놓일 수 없다. 최 교수는 주어진 거리 제약을 모두 만족하도록 모든 소국을 x축 위에 놓을 수 있는지 판단하고자 한다.

예를 들어 $n = 3$이고 소국 $1$번과 $2$번 사이의 거리가 $4$, 소국 $1$번과 $3$번 사이의 거리도 $4$라면, 세 소국을 각각 위치 $0, 4, -4$에 놓을 수 있고 $0, -4, 4$에 놓을 수도 있다. 그러나 $0, 4, 4$나 $0, -4, -4$처럼 놓을 수는 없다.

입력은 표준 입력으로 주어진다. 첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $m$이 주어진다. $n$은 진한 소국의 수, $m$은 거리가 알려진 소국 쌍의 수이며 $1 \le n \le 3000$, $1 \le m \le 300000$이다. 이어지는 $m$개의 줄에는 각각 세 정수 $u$, $v$, $d$가 주어지며, 이는 소국 $u$번과 $v$번이 거리 $d$만큼 떨어져 있음을 뜻한다($1 \le d \le 3 \times 10^8$). 사로국($1$번)과 다른 모든 소국 사이의 거리는 항상 입력에 포함된다.

각 테스트 케이스마다 정확히 두 줄을 출력한다. 첫 줄에는 소국의 수 $n$을 출력한다. 둘째 줄에는, 모든 거리 제약과 '서로 다른 지점' 조건을 만족하는 배치가 존재하면 소국 $1$번부터 $n$번까지의 위치 $x_1\ x_2\ \dots\ x_n$을 공백으로 구분해 출력하고, 그런 배치가 없으면 impossible을 출력한다. 사로국은 항상 $x_1 = 0$이다.

유효한 배치가 여러 개이면, 위치 수열 $(x_1, x_2, \dots, x_n)$을 앞에서부터 차례로 비교하여 사전순으로 가장 작은 것(처음으로 값이 달라지는 자리에서 더 작은 정수를 갖는 배치)을 출력한다.