Jogging in the Park

The Outer Park is very well suited for jogging. Inside the park, there are $n$ glades, numbered from 1 to $n$. The glades are connected by $m$ trails. The $i$-th trail connects glades $a_i$ and $b_i$ and has length $c_i$ meters. All trails can be walked in both directions. The main entrance is at glade 1.

Your friends each prepared a route that starts at the entrance and moves from glade to glade along trails. At the end of the run, all friends want to reach glade $n$ at the same time, where a cafe is. Some routes do not end at glade $n$, and the routes may have different lengths. All friends run at the same speed.

Extend each route so that it starts with the same glades as the original, ends at glade $n$, and has exactly the same length as every other extended route. An original or extended route may use the same trail more than once.

The first line contains two integers $n$ and $m$ ($2 \le n \le 50$; $1 \le m \le \frac{n(n-1)}{2}$), the number of glades and trails. Each of the next $m$ lines contains three integers $a_i$, $b_i$, and $c_i$ ($1 \le a_i, b_i \le n$; $a_i \ne b_i$; $1 \le c_i \le 10^6$), the glades connected by the $i$-th trail and its length.

The next line contains a single integer $k$ ($2 \le k \le 50$), the number of friends. Each of the next $k$ lines contains $l_i$ ($2 \le l_i \le 50$), the number of glades in the route of the $i$-th friend, followed by $l_i$ integers $g_{i,1}, \ldots, g_{i,l_i}$ ($1 \le g_{i,j} \le n$), the glades of that route.

All unordered pairs $(a_i, b_i)$ are distinct. For every $i$, $g_{i,1} = 1$. For every $j$ between 1 and $l_i - 1$, there is a trail between $g_{i,j}$ and $g_{i,j+1}$.

If it is impossible to extend all the routes, print a single integer -1. Otherwise, print $k$ lines. The $i$-th line contains $p_i$ ($p_i \ge l_i$) followed by $p_i$ integers $h_{i,1}, \ldots, h_{i,p_i}$ ($1 \le h_{i,j} \le n$), the glades of the $i$-th extended route.

For every $i$, $h_{i,p_i} = n$. For every $j$ between 1 and $p_i - 1$, there is a trail between $h_{i,j}$ and $h_{i,j+1}$. For every $j$ between 1 and $l_i$, $h_{i,j} = g_{i,j}$. The total length of all extended routes must be the same.

The sum of all $p_i$ must not exceed $2 \cdot 10^6$. If a valid extension exists, one exists with the sum of all $p_i$ at most $2 \cdot 10^6$.