CF229B Planets

## 题面 在宇宙里有 $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 。 ## 输入输出样例 略 ## 样例解释 对于样例1，Jack有3种方案： 1. 直接从1->4，在时刻8到达星球4。 2. 先从1->3，在时刻3到达，但是此时（时刻3和时刻4）有其他人在使用通道，他只能在时刻5出发，在时刻8到达星球4。 3. 先从1->2，在时刻2到达，再从2->4，在时刻7到达。 所以他最早可以在时刻7到达。 对于样例2，Jack不能通过传送从星球1前往星球3。 感谢@星烁晶熠辉 提供的翻译和@Styx 提供的建议

In the first sample Jack has three ways to go from planet 1. If he moves to planet 4 at once, he spends 8 seconds. If he transfers to planet 3, he spends 3 seconds, but as other travellers arrive to planet 3 at time 3 and 4, he can travel to planet 4 only at time 5, thus spending 8 seconds in total. But if Jack moves to planet 2, and then — to planet 4, then he spends a total of only $ 2+5=7 $ seconds. In the second sample one can't get from planet 1 to planet 3 by moving through stargates.