题目描述

在宇宙里有 $n$ 个星球，分别编号为 $1,2,...,n$。Jack 现在在 $1$ 号星球上，他要去 $n$ 号星球。已知一些星球之间有双向的传送通道，Jack 可以通过这些传送通道移动。每次传送需要一些时间，在不同的星球之间传送也可能需要不同时间。

当有其他人在使用这个星球的传送通道时，Jack 无法离开这个星球。比如，如果有人在 $t$ 时刻使用通道，那 Jack 只能在 $t+1$ 时刻离开（如果 $t+1$ 时刻没有人在使用通道）。

现在，Jack 想请你计算他最早可以在哪个时刻到达 $n$ 号星球。Jack 在 $0$ 时刻出发。

输入格式

输入的第一行包括两个由空格分割的整数，星球数 $n\ (2≤n≤10^5)$ 和传送通道数 $m\ (0≤m≤10^5)$。

接下来的 $m$ 行，每行包括了 $3$ 个整数 $a$，$b$ 和 $c\ (1≤a,b≤n$，$a≠b$，$1≤c≤10^4)$，表示星球 $a$ 与星球 $b$ 之间有一条耗时为 $c$ 的传送通道。

接下来的 $n$ 行，第 $i$ 行表示第 $i$ 个星球的传送通道的使用情况。每行首先是一个整数 $k_i$，表示一共有 $k_i$ 个时刻这个星球的传送通道在被使用，接下来 $k_i$ 个整数 $t_{ij}\ (0≤t_{ij}≤10^9)$ 表示在 $t_{ij}$ 时刻 $i$ 星球的传送通道正被他人使用。所有 $k_i$ 的和不超过 $10^5$。 $t_{ij}$ 按照升序排列。

输出格式

输出一行，一个整数，表示 Jack 可以最早在哪个时刻到达 $n$ 号星球。如果他无法通过这些传送通道到达，输出 $-1$。

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

7

Jack 有 $3$ 种方案：

1. 直接从 $1\to 4$，在时刻 $8$ 到达星球 $4$。
2. 先从 $1\to 3$，在时刻 $3$ 到达，但是此时（时刻 $3$ 和时刻 $4$）有其他人在使用通道，他只能在时刻 $5$ 出发，在时刻 $8$ 到达星球 $4$。
3. 先从 $1\to 2$，在时刻 $2$ 到达，再从 $2\to 4$，在时刻 $7$ 到达。

所以他最早可以在时刻 $7$ 到达。

3 1
1 2 3
0
1 3
0

-1