外公园非常适合慢跑。公园内有 $n$ 个林间空地，编号从 $1$ 到 $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 \neq b_i; 1 \le c_i \le 10^6$)，表示第 $i$ 条小径连接的空地编号及其长度。

下一行包含一个整数 $k$ ($2 \le k \le 50$)，表示你慢跑朋友的数量。

接下来的 $k$ 行，每行包含一个整数 $l_i$ ($2 \le l_i \le 50$)，表示第 $i$ 位朋友路线中的空地数量，随后是 $l_i$ 个整数 $g_{i,1}, g_{i,2}, \dots, 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}, h_{i,2}, \dots, 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$ 的方案。

样例

输入 1

4 4
1 2 10
2 3 30
2 4 30
1 4 100
3
2 1 2
3 1 2 3
2 1 4

输出 1

5 1 2 4 2 4
5 1 2 3 2 4
2 1 4