공원에서 조깅하기

외곽 공원은 조깅하기에 아주 좋다. 공원 안에는 1번부터 $n$번까지 번호가 붙은 광장이 $n$개 있다. 광장들은 $m$개의 산책로로 이어져 있다. $i$번째 산책로는 광장 $a_i$와 $b_i$를 잇고, 길이는 $c_i$미터이다. 모든 산책로는 양방향으로 지날 수 있다. 정문은 1번 광장에 있다.

친구들은 각자 정문에서 출발해 산책로를 따라 광장을 옮겨 다니는 경로를 짰다. 달리기가 끝나면 모두 같은 시각에 카페가 있는 $n$번 광장에 도착하려고 한다. 그런데 경로 중에는 $n$번 광장에서 끝나지 않는 것도 있고, 경로마다 길이도 다르다. 친구들은 모두 같은 속도로 달린다.

각 경로를 원래 경로와 같은 광장으로 시작하고, $n$번 광장에서 끝나며, 다른 모든 확장 경로와 길이가 정확히 같도록 늘려라. 원래 경로와 확장 경로 모두 같은 산책로를 여러 번 지나도 된다.

첫 줄에 광장 수와 산책로 수를 나타내는 정수 $n$, $m$이 주어진다($2 \le n \le 50$; $1 \le m \le \frac{n(n-1)}{2}$). 이어지는 $m$개의 줄에는 각각 정수 $a_i$, $b_i$, $c_i$가 주어진다($1 \le a_i, b_i \le n$; $a_i \ne b_i$; $1 \le c_i \le 10^6$). 이는 $i$번째 산책로가 잇는 두 광장과 그 길이다.

다음 줄에는 친구 수를 나타내는 정수 $k$가 주어진다($2 \le k \le 50$). 이어지는 $k$개의 줄에는 각각 $i$번째 친구 경로의 광장 수 $l_i$($2 \le l_i \le 50$)와, 뒤이어 그 경로의 광장 $g_{i,1}, \ldots, g_{i,l_i}$($1 \le g_{i,j} \le n$)가 주어진다.

모든 무순서쌍 $(a_i, b_i)$는 서로 다르다. 모든 $i$에 대해 $g_{i,1} = 1$이다. $1$부터 $l_i - 1$까지의 모든 $j$에 대해 광장 $g_{i,j}$와 $g_{i,j+1}$ 사이에 산책로가 있다.

모든 경로를 늘릴 수 없으면 정수 -1 하나만 출력한다. 그렇지 않으면 $k$개의 줄을 출력한다. $i$번째 줄에는 $p_i$($p_i \ge l_i$)와 뒤이어 $p_i$개의 정수 $h_{i,1}, \ldots, h_{i,p_i}$($1 \le h_{i,j} \le n$)를 출력한다. 이는 $i$번째 확장 경로의 광장 순서이다.

모든 $i$에 대해 $h_{i,p_i} = n$이어야 한다. $1$부터 $p_i - 1$까지의 모든 $j$에 대해 광장 $h_{i,j}$와 $h_{i,j+1}$ 사이에 산책로가 있어야 한다. $1$부터 $l_i$까지의 모든 $j$에 대해 $h_{i,j} = g_{i,j}$이어야 한다. 모든 확장 경로의 총 길이는 같아야 한다.

모든 $p_i$의 합은 $2 \cdot 10^6$을 넘으면 안 된다. 유효한 확장이 존재한다면 모든 $p_i$의 합이 $2 \cdot 10^6$ 이하인 확장도 존재함이 보장된다.