Description

肖肖制药成功，现在需要将药品运输出去贩卖。在运输途中肖肖要经过一个奇怪的地界。这里存在$n$个区域，两区域之间可能存在一条（或多条）长度为$w$的双向道路。在这里，1号区域为入口，$n$号区域为出口。神奇的是这里的某些区域上存在着某种能量（当然，任意一个区域都可能有一种或多种能量，也可能没有能量）。肖肖只能在具有相同能量的区域中选一个去走，否则所有的能量都将爆炸引发塌方。例如：区域$1$、区域$2$、区域$3$都存在能量$1$，那么如果在行走的过程中经过了区域$1$，那就不能再经过区域$2$或区域$3$了。

现在肖肖想知道走出这个地界所需的最短路程是多少？

Input Format

第一行输入一个整数$T$（$1 \le T \le 10$），表示共有$T$组测试样例。

对于每组测试样例：

第一行输入三个整数$n，m，k$（$1 \le n, m \le 200, 1 \le k \le 10$）。其中，$n，m$分别表示区域和道路的个数，$k$表示共存在$k$种能量。

接下来$m$行，每行输入三个整数$u，v，w$（$1 \le u, v \le n, 1 \le w \le 10^5$）表示区域$u$和区域$v$之间存在一条长度为$w$的路。

接下来$k$行，对于第$i$行，首先输入一个正整数$q$（$1 \le q \le n$），表示有$q$个区域存在能量$i$。接下来输入$q$个正整数$x_j$($1 \le x_j \le n$)表示区域$x_j$存在能量$i$。

Output Format

对于每组测试样例，输出一行，包含一个整数。表示肖肖所需要通过该地界的最短路。如果不能通过，则输出$“impossible”$（不输出双引号）

1
8 12 2
1 2 1
2 4 3
1 3 1
2 5 2
3 4 1
3 5 1
3 6 1
5 6 1
4 5 2
5 7 2
7 8 1
6 7 1
3 3 5 6
2 4 7

6

Source

1816 Online Judge 10.100.0.232