题目描述

一条城际铁路网共有 $n$ 个车站，编号为 $1 \sim n$。

车站之间有 $m$ 条双向铁路。每条铁路连接两个车站，列车在这条铁路上运行需要固定时间 $w$。

Aki 需要从车站 $1$ 出发，尽快到达车站 $n$。他在时刻 $0$ 位于车站 $1$。

但是每个车站都有一些禁止发车时刻。如果 Aki 在车站 $i$ 的某个时刻 $t$ 想要发车，而 $t$ 恰好属于该车站的禁止发车时刻表，那么他不能在这个时刻离开，只能继续等待。

更准确地说：

• 如果 Aki 在时刻 $t$ 到达车站 $i$；
• 只要时刻 $t$ 被禁止发车，他就必须等待到 $t+1$；
• 若新的时刻仍然被禁止发车，就继续等待；
• 直到遇到第一个允许发车的时刻，才能选择一条铁路离开。

注意：一旦到达终点车站 $n$，旅程立即结束，不需要再考虑终点的禁止发车时刻。

请你求出从车站 $1$ 到车站 $n$ 的最早到达时间。如果无法到达，输出 $-1$。

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行，每行三个整数 $u, v, w$，表示车站 $u$ 和车站 $v$ 之间有一条双向铁路，运行时间为 $w$。

接下来 $n$ 行，第 $i$ 行先给出一个整数 $k_i$，表示车站 $i$ 的禁止发车时刻个数；随后给出 $k_i$ 个严格递增的整数，表示这些禁止发车时刻。

数据范围：

• $1 \le n \le 5 \times 10^4$
• $1 \le m \le 10^5$
• $1 \le w \le 10^6$
• $0 \le k_i$
• 所有 $k_i$ 的总和不超过 $3 \times 10^5$
• 禁止发车时刻均为非负整数，且不超过 $10^9$

输出格式

输出一个整数，表示最早到达车站 $n$ 的时间；如果无法到达，输出 -1。

4 4
1 2 2
2 4 2
1 3 1
3 4 5
2 0 1
1 2
0
1 1

6

4 2
1 2 3
3 4 1
0
0
0
0

-1