Bytie-boy 是 Byteburg 最年幼的居民之一。他才刚刚学会读写，不过他已经大到可以独自去上学了。每天早上，他离开家去接所有的朋友；只有当所有人都集合完毕后，整个小组才会一起去学校。

有一天，老师要求 Bytie 准备一份他上学路上所经过的街道列表，并在下一节课上大声朗读出来。很快大家发现这份列表非常长，长到需要消耗大量的纸张。因此，大家决定让 Bytie 只写下他所经过的每条街道名称的首字母。Byteburg 的街道全部是单向的，且每一条街道连接两个不同的路口。

在朗读字母列表时，Bytie 只会在接到朋友的地方停顿。因此，他行进路线的每一段都可以被视为一个单独的单词。朗读对这个男孩来说仍然有些困难：有时他会从右向左读，而不是从左向右读。所以他可能会把单词 milk 读作 milk，也可能读作 klim。由于 Bytie 的父母了解他的困难，他们决定通过寻找一条路线来帮助他，使得该路线的每一段无论从左向右读还是从右向左读都是一样的（即回文）。出于显而易见的原因，父母还希望每一段（单词）尽可能短。他们请求你的帮助。

编写一个程序，完成以下任务：

• 从标准输入读取城市描述。
• 确定一条从 Bytie 家到学校的路线，使得每一段路线都尽可能短，且其描述从左向右读和从右向左读完全相同。
• 将描述（并适当分隔各段）输出到标准输出。

标准输入的第一行包含两个整数 $n$ 和 $m$，由一个空格分隔（$2 \le n \le 400$，$1 \le m \le 60\,000$）。它们分别表示 Byteburg 的路口数量和连接它们的街道数量。接下来的 $m$ 行描述了街道。第 $(i+1)$ 行包含三个值：$x_i$，$y_i$，$c_i$（$1 \le x_i \le n$，$1 \le y_i \le n$，$x_i \neq y_i$）；它们分别表示街道的起点、终点以及街道名称的首字母，并由空格分隔。字母为小写英文字母。任意两个路口之间在每个方向上最多只有一条街道（即一个方向最多一条，反方向也最多一条）。接下来的行包含一个整数 $d$（$2 \le d \le 100$），表示 Bytie 在去学校的路上经过的路口数量。下一行包含 $d$ 个整数 $s_i$（$1 \le s_i \le n$），同样由空格分隔。这意味着 Bytie 住在 $s_1$ 号路口，学校位于 $s_d$ 号路口，在路上 Bytie 会依次接住住在 $s_2, s_3, \dots, s_{d-1}$ 号路口的朋友。列表中每两个相邻的路口编号均不相同，但列表中可能存在相同的编号。此外，如果无法按照任务中设定的限制从一个路口到达另一个路口，Bytie 会走捷径，并在纸上什么也不写。

输出应包含 $d-1$ 行。第 $i$ 行应包含一个数字 $r_i$ 和一个字符序列 $w_i$，由一个空格分隔。数字 $r_i$ 表示连接路口 $s_i$ 和 $s_{i+1}$ 且满足任务条件的路线的最小长度，而 $w_i$ 是该路线中街道首字母的序列。如果两个路口之间不存在满足上述条件的路线，则输出 -1。可能存在多种可能的序列 $w_i$，这种情况下输出任意一种即可。

样例

输入格式 1

6 7
1 2 a
1 3 x
1 4 b
2 6 l
3 5 y
4 5 z
6 5 a
3
1 5 3

输出格式 1

3 ala
-1