题目描述

Goa'uld Apophis 又一次抓走了 Jack O'Neill 的团队！Jack 本人侥幸逃脱，但那时 Apophis 的飞船已经跃迁进了超空间。不过 Jack 知道 Apophis 将在哪颗行星降落。为了营救伙伴，Jack 必须反复穿越星际之门到达那颗行星。

星系中共有 $n$ 颗行星，编号从 1 到 $n$。Jack 在 1 号行星上，Apophis 将降落在 $n$ 号行星上。某些行星对之间可以通过星际之门双向移动，转移需要一段正整数秒数（不同行星对之间可能不同）。Jack 在时刻 0 出发。

可能有其他旅行者恰好到达 Jack 当前所在的行星。这种情况下，Jack 必须等待恰好 1 秒才能使用星际之门。也就是说，若在时刻 $t$ 有别的旅行者到达该行星，Jack 最早只能在时刻 $t+1$ 通过星际之门——除非时刻 $t+1$ 又有旅行者到达同一颗行星。

给定行星之间的转移时间，以及各行星上其他旅行者到达的时刻，求 Jack 到达 $n$ 号行星所需的最短时间。

输入格式

第一行包含两个用空格隔开的整数：$n$（$2 \le n \le 10^5$）表示星系中的行星数，$m$（$0 \le m \le 10^5$）表示可用星际之门移动的行星对数。接下来 $m$ 行，每行三个整数：第 $i$ 行给出星际之门连通的两颗行星 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$），以及它们之间的转移时间 $c_i$（单位：秒，$1 \le c_i \le 10^4$）。保证任意两颗行星之间至多有一条星际之门连接。

接下来 $n$ 行：第 $i$ 行先是一个整数 $k_i$（$0 \le k_i \le 10^5$），表示其他旅行者到达第 $i$ 颗行星的时刻数；随后是 $k_i$ 个互不相同、按升序排列的整数 $t_{ij}$（$0 \le t_{ij} \lt 10^9$），即这些到达时刻。

输出格式

输出一个数——Jack 从 1 号行星到达 $n$ 号行星所需的最少时间。如果 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

3 1
1 2 3
0
1 3
0

-1

说明/提示

第一组样例中，Jack 有三种走法。若直接前往 4 号行星，耗时 8 秒；若先到 3 号行星，耗时 3 秒，但由于其他旅行者在时刻 3 和 4 到达 3 号行星，他只能等到时刻 5 再前往 4 号行星，总共还是 8 秒；而若先到 2 号行星、再到 4 号行星，总共只需 $2+5=7$ 秒。

第二组样例中，从 1 号行星出发无法通过星际之门到达 3 号行星。