← 返回题目列表

Codeforces · 229/B

B. 行星

中文机器翻译题面 查看原题

Goa'uld Apophis再次俘虏了Jack O'Neill的队伍!杰克本人得以逃脱,但此时阿波菲斯的飞船已经跃入超空间。但杰克知道阿波菲斯将登陆哪个星球。为了拯救他的朋友,杰克必须多次穿越星际之门才能到达这个星球。

银河系总共有 n 个行星,索引号为 1 到 n。杰克在索引为1的行星上,阿波菲斯将降落在索引为n的行星上。杰克可以通过星门在一些行星对之间移动(他可以双向移动);转移需要一定的时间,而且对于不同的行星对来说,可能需要不相等的秒数。杰克在时间 0 开始他的旅程。

可能有其他旅行者正在抵达杰克当前所在的星球。在这种情况下,杰克必须等待整整1秒才能使用星门。也就是说,如果在时间t有另一个旅行者到达该星球,杰克只能在时间t+1通过星门,除非有更多的旅行者在时间t+1到达同一个星球。

了解行星之间的旅行时间信息,以及杰克在特定行星上无法使用星门的时间,确定他可以到达索引为 n 的行星的最短时间。

输入

第一行包含两个以空格分隔的整数:n (2 ≤ n ≤ 105),银河系中的行星数量,m (0 ≤ m ≤ 105) - 杰克可以使用星门在其之间旅行的行星对数量。接下来是m行,每行包含三个整数:第i行包含通过星门连接的行星ai和bi(1≤ai,bi≤n,ai≠bi)的数量,以及这些行星之间的整数传输时间(以秒为单位)ci(1≤ci≤104)。保证任意一对行星之间至多有一个星门连接。

接下来是 n 行:第 i 行包含一个整数 ki (0 ≤ ki ≤ 105),表示其他旅行者到达索引为 i 的行星的时刻数。然后是 ki 个不同的空格分隔整数 tij (0 ≤ tij < 109),按升序排序。整数 tij 表示在时间 tij (以秒为单位)另一位旅行者到达行星 i。保证所有ki的总和不超过105。

输出

打印一个数字——杰克从行星 1 到行星 n 所需的最短时间。如果 Jack 在任何时间内都无法到达 n 行星,则打印数字 -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

注意

在第一个示例中,杰克从行星 1 出发有三种方式。如果他立即移动到行星 4,他将花费 8 秒。如果他转移到行星 3,他会花费 3 秒,但由于其他旅行者在时间 3 和 4 到达行星 3,他只能在时间 5 到达行星 4,因此总共花费了 8 秒。但如果杰克移动到 2 号行星,然后移动到 4 号行星,那么他总共只花费 2 + 5 = 7 秒。

在第二个示例中,人们无法通过星门从行星 1 到达行星 3。