一个铁路网络由若干个节点和连接它们的单向铁轨组成。每条铁轨只能单向通行。两个节点之间可以由任意数量的铁轨连接，但没有自环（即没有铁轨将一个节点连接到它自身）。

当列车的第一节车厢（称为机车，即火车头）到达某条铁轨的终点节点时，司机需要选择一条从该节点出发的铁轨并驶入。然而，根据列车当前正在通过的铁轨类型，存在以下限制：

1. 直轨（Straight track）——对于这种类型的铁轨，司机无法进行选择，因为无论该节点有多少条出发铁轨，都只有唯一一条允许驶入的后续铁轨。
2. 带分叉的铁轨（Track with a switch）——在这条铁轨的尽头，司机需要从两条可选的铁轨中选择一条驶入。

不论何种类型，所有铁轨的长度均为 $1$ 千米。

给你一列由 $k$ 节车厢（包括机车）组成的冗长货运列车。每节车厢的长度为 $25$ 米，车厢之间的间距忽略不计。最初，整列火车停在铁路网络之外的出发车库中，且机车的前端恰好位于节点 $1$。

在旅程开始时，列车可以驶入从节点 $1$ 出发的任意铁轨。目标是尽快驶入节点 $n$。当列车的前端到达节点 $n$ 时，机车及所有其他车厢将驶入铁路网络之外的到达车库。所有车厢同时以恒定速度运动。

列车完成这次旅程所需行驶的最短距离是多少？这里有一个重要的限制：列车不能自交。也就是说，在任何固定的时刻，任何节点上最多只能存在列车的一个点。唯一的例外是：机车的最前端和列车尾部的最后一点可以同时处于同一个节点。请参阅样例以获得进一步的解释。

输入格式

第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n, m, k \le 500$），分别表示铁路网络中的节点数、铁轨数以及列车的车厢数。

接下来的 $m$ 行描述铁轨。每条铁轨的描述以三个整数 $u_i$、$v_i$ 和 $c_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$，$1 \le c_i \le 2$）开始，分别表示该铁轨的起点节点、终点节点以及司机通过该铁轨后可以选择的后续铁轨数量。紧接着是 $c_i$ 个不同的整数 $r_{i,j}$（$1 \le r_{i,j} \le m$），表示通过第 $i$ 条铁轨后，列车可以驶入的铁轨编号。保证所有这些铁轨都以节点 $v_i$ 为起点。

输出格式

输出一个整数，表示列车必须行驶的最短距离（以米为单位）。如果列车无法到达位于节点 $n$ 的到达车库，则输出 "No chance"（不含引号）。

样例

输入样例 1

4 6 80
1 3 1 4
2 1 1 1
2 3 2 4 5
3 2 2 2 3
3 4 1 6
4 1 1 1

输出样例 1

6000

输入样例 2

6 7 150
1 2 1 2
2 3 1 3
3 4 1 4
4 5 1 5
5 3 1 6
3 6 1 7
6 3 1 6

输出样例 2

No chance

说明

在第一个样例中，列车的最优路径为：出发车库 $\to 1 \to 3 \to 2 \to 3 \to 4 \to$ 到达车库。

列车的运动过程如下图所示，图中列车以 10 节车厢示意。

在第二个样例中，列车无法避免在节点 3 处发生自交，因此无法到达到达车库。