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 提供的建议

题目描述

Goa'uld Apophis captured Jack O'Neill's team again! Jack himself was able to escape, but by that time Apophis's ship had already jumped to hyperspace. But Jack knows on what planet will Apophis land. In order to save his friends, Jack must repeatedly go through stargates to get to this planet. Overall the galaxy has $ n $ planets, indexed with numbers from 1 to $ n $ . Jack is on the planet with index 1, and Apophis will land on the planet with index $ n $ . Jack can move between some pairs of planets through stargates (he can move in both directions); the transfer takes a positive, and, perhaps, for different pairs of planets unequal number of seconds. Jack begins his journey at time 0. It can be that other travellers are arriving to the planet where Jack is currently located. In this case, Jack has to wait for exactly 1 second before he can use the stargate. That is, if at time $ t $ another traveller arrives to the planet, Jack can only pass through the stargate at time $ t+1 $ , unless there are more travellers arriving at time $ t+1 $ to the same planet. Knowing the information about travel times between the planets, and the times when Jack would not be able to use the stargate on particular planets, determine the minimum time in which he can get to the planet with index $ n $ .

输入输出格式

输入格式

The first line contains two space-separated integers: $ n $ ( $ 2<=n<=10^{5} $ ), the number of planets in the galaxy, and $ m $ ( $ 0<=m<=10^{5} $ ) — the number of pairs of planets between which Jack can travel using stargates. Then $ m $ lines follow, containing three integers each: the $ i $ -th line contains numbers of planets $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i},b_{i}<=n $ , $ a_{i}≠b_{i} $ ), which are connected through stargates, and the integer transfer time (in seconds) $ c_{i} $ ( $ 1<=c_{i}<=10^{4} $ ) between these planets. It is guaranteed that between any pair of planets there is at most one stargate connection. Then $ n $ lines follow: the $ i $ -th line contains an integer $ k_{i} $ ( $ 0<=k_{i}<=10^{5} $ ) that denotes the number of moments of time when other travellers arrive to the planet with index $ i $ . Then $ k_{i} $ distinct space-separated integers $ t_{ij} $ ( $ 0<=t_{ij}&lt;10^{9} $ ) follow, sorted in ascending order. An integer $ t_{ij} $ means that at time $ t_{ij} $ (in seconds) another traveller arrives to the planet $ i $ . It is guaranteed that the sum of all $ k_{i} $ does not exceed $ 10^{5} $ .

输出格式

Print a single number — the least amount of time Jack needs to get from planet 1 to planet $ n $ . If Jack can't get to planet $ n $ in any amount of time, print number -1.

输入输出样例

输入样例 #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

输出样例 #1

7

输入样例 #2

3 1
1 2 3
0
1 3
0

输出样例 #2

-1

说明

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.