题目描述

你想开发一个应用程序，帮助游客在一座大型植物园中导航。

这并不容易：植物园内有许多蜿蜒的小路和岔路口，可供选择的方向很多，因此“向右转”或“继续向北走”之类的传统指令并不合适。相反，应用程序应当利用植物园最丰富的资源——种类繁多、颜色各异的奇花异草。

每当用户位于一个路口时，应用程序都知道用户所在的位置，并会显示一种特定颜色。用户随后选择一条从当前路口出发、沿途能够看到该颜色的路径前进。如果该颜色在多条出发路径上都能看到，用户可以任意选择其中一条。

你获得了一份植物园的完整模型，其中包含 $n$ 个路口（编号为 $1$～$n$）和 $m$ 条连接路口的路径。为了维持秩序，每条路径只能沿给定方向通行。

目前园内一共展现出 $k$ 种不同颜色，编号为 $1$～$k$。对于每条路径，给定从其起点观察时，沿该路径能够看到的全部颜色。

用户当前位于路口 $1$，希望到达路口 $n$。可以假设用户会完全遵守应用程序给出的指令；但是，当指定颜色对应多条可选路径时，必须假设用户会作出对你最不利的选择。

当应用程序采用最优指令策略时，到达目标最多需要多少时间？

输入格式

输入包含：

• 第一行三个整数 $n,m,k$：
  • $n$（$1\le n\le 5\times 10^5$）表示路口数量；
  • $m$（$1\le m\le 5\times 10^5$）表示有向路径数量；
  • $k$（$1\le k\le 1000$）表示不同颜色的数量。
• 接下来用 $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,c_2,\ldots,c_\ell$（$1\le c_i\le k$），表示从路口 $u$ 出发观察时，沿该路径能够看到的颜色。

所有路径的 $\ell$ 之和不超过 $5\times 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

输出

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

输出

impossible