这条宏伟的小径拥有红色、白色、紫色和绿色。来源：慕尼黑宁芬堡植物园。

你想构建一个应用程序来帮助人们在大型植物园中导航。这很困难，因为园内有许多蜿蜒的小径和交叉路口，提供了多种选择，使得“向右转”或“继续向北走”等传统导航方式不再适用。相反，该应用程序应该利用植物园最大的资源：种类繁多的异国植物及其多样的颜色。每当用户到达一个交叉路口时，应用程序都会知道他们所在的位置，并相应地显示一种特定的颜色。用户随后会沿着可以看到该颜色的小径行走。如果该颜色可以在从该交叉路口出发的多条小径上看到，用户可以自由选择其中任何一条小径。

你已经得到了一个植物园的完美模型，包含 $n$ 个交叉路口（编号从 $1$ 到 $n$）以及连接它们之间的 $m$ 条小径。为了保持秩序，每条小径只能按给定的方向使用。目前，植物呈现出 $k$ 种不同的颜色（编号从 $1$ 到 $k$），对于每条小径，你都会得到一个列表，列出了从该小径的起点交叉路口观察时，沿途可见的所有颜色。用户目前位于交叉路口 $1$，想要前往交叉路口 $n$。你可以假设用户会完美地遵循应用程序的指示，但每当面临多种选择时（因为给定的颜色在多条小径上都可见），你必须假设他们会做出最糟糕的选择。当你的应用程序给出最佳指令时，到达目标需要多长时间？

输入格式

输入包含：

• 一行包含交叉路口的数量 $n$ ($1 \le n \le 5 \cdot 10^5$)，小径的数量 $m$ ($1 \le m \le 5 \cdot 10^5$) 以及不同颜色的数量 $k$ ($1 \le k \le 1\,000$)。
• $m$ 组描述有向小径的行，每组格式如下：
  • 一行包含三个整数 $u, v$ 和 $t$ ($1 \le u, v \le n, 1 \le t \le 10^6$)，表示该小径从交叉路口 $u$ 通向交叉路口 $v$，且走完这条小径需要 $t$ 秒。
  • 一行包含一个整数 $\ell$ ($1 \le \ell \le k$)，后跟 $\ell$ 个不同的整数 $c_1, \dots, c_\ell$ ($1 \le c_i \le k$，对于每个 $i$)，列出了出现在该小径上的颜色。

所有小径的 $\ell$ 之和不超过 $5 \cdot 10^5$。请注意，正如你在植物园中想象的那样，小径可以通回它开始的交叉路口，并且一对交叉路口之间可以存在多条小径。此外，不保证每个交叉路口都能通过小径到达。

输出格式

如果无法引导用户到达交叉路口 $n$，输出 impossible。否则，输出一个整数，表示到达目标所需的时间（以秒为单位）。我们仅考虑沿着小径行走所花费的时间。

样例

输入格式 1

4 6 2
1 2 6
1 1
1 3 3
1 2
2 3 5
1 2
2 4 8
1 1
3 1 4
2 1 2
3 4 3
1 1

输出格式 1

14

输入格式 2

3 4 3
1 2 300
2 1 2
2 1 2000
2 3 1
1 3 80
2 2 1
2 2 42
1 2

输出格式 2

impossible