CF229B.Planets

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.

Goa'uld 阿波菲斯再次俘获了杰克·奥尼尔小队！杰克本人成功逃脱，但此时阿波菲斯的飞船早已跃入超空间。不过，杰克知道阿波菲斯将降落在哪颗行星上。为了营救他的队友，杰克必须多次穿越星门，抵达该行星。

整个银河系共有 $n$ 颗行星，编号为 $1$ 到 $n$。杰克起始于编号为 $1$ 的行星，而阿波菲斯将降落在编号为 $n$ 的行星。杰克可通过星门在某些行星对之间往返（双向通行）；每次穿越所需时间为正数，且不同行星对之间的穿越时间可能不等。杰克于时刻 $0$ 开始旅程。

有可能其他旅行者会在杰克当前所在的行星着陆。此时，杰克必须恰好等待 $1$ 秒后才能使用该行星上的星门。即：若在时刻 $t$ 有其他旅行者抵达杰克所在的行星，则杰克最早可在时刻 $t+1$ 使用星门——除非在时刻 $t+1$ 还有更多旅行者抵达同一颗行星。

已知各行星对之间的穿越时间，以及杰克在特定行星上无法使用星门的具体时刻，请确定杰克抵达编号为 $n$ 的行星所需的最短时间。

The first line contains two space-separated integers: n (2 ≤ n ≤ 105), the number of planets in the galaxy, and m (0 ≤ m ≤ 105) — 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 ≤ 104) 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 ≤ 105) 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 < 109) 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 105.

第一行包含两个以空格分隔的整数：$n$（$2 \leq n \leq 10^5$），表示银河系中行星的数量；以及 $m$（$0 \leq m \leq 10^5$），表示 Jack 可通过星门在其中往返的行星对的数量。接下来是 $m$ 行，每行包含三个整数：第 $i$ 行包含行星编号 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$，且 $a_i \neq b_i$），表示这两颗行星之间存在星门连接，以及它们之间的传送时间（单位：秒）$c_i$（$1 \leq c_i \leq 10^4$）。保证任意两颗行星之间至多存在一条星门连接。

随后是 $n$ 行：第 $i$ 行包含一个整数 $k_i$（$0 \leq k_i \leq 10^5$），表示抵达编号为 $i$ 的行星的其他旅行者的时刻数量。接着是 $k_i$ 个互不相同、以空格分隔的整数 $t_{ij}$（$0 \leq t_{ij} < 10^9$），按升序排列。整数 $t_{ij}$ 表示在时刻 $t_{ij}$（单位：秒）有另一位旅行者抵达行星 $i$。保证所有 $k_i$ 的总和不超过 $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.

输出一个整数——Jack 从行星 1 到达行星 $n$ 所需的最少时间。如果 Jack 无法在任何时间内到达行星 $n$，则输出数字 -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.

在第一个样例中，Jack 有三种方式从行星 1 出发。如果他直接前往行星 4，则耗时 8 秒；如果他先转移到行星 3，则耗时 3 秒，但由于其他旅行者分别于时刻 3 和 4 抵达行星 3，他只能等到时刻 5 才能从行星 3 前往行星 4，因此总耗时为 8 秒；但如果 Jack 先前往行星 2，再从行星 2 前往行星 4，则总耗时仅为 $2 + 5 = 7$ 秒。

在第二个样例中，无法通过星门从行星 1 到达行星 3。