简单游走

题目描述

有一张 $n$ 个点， $m$ 条边的无向图，点从 $1$ 到 $n$ 标号。

时刻 $0$ 时，你在结点 $1$ 。你需要用最少的时间从结点 $1$ 走到结点 $n$ 。通过 $m$ 条边中的每一条都要花一定的时间。

每个结点会有可能在某些时刻被限制。一个结点 $x$ 在时刻 $T$ 被限制，意味着这个结点的人在时刻 $T$ 不能从这个点 $x$ 走出去。

你只能在整数时刻进出某个结点，一个结点可以逗留任意非负整数时间。

现在，请问你最少需要多少时间能从结点 $1$ 走到结点 $n$ 。

第一行两个整数 $n$ ， $m$ 。表示有 $n$ 个节点， $m$ 条边。

接下来 $m$ 行，每行 $3$ 个整数 $u$ ， $v$ ， $w$ ，分别表示这条边连接的两个节点 $u$ ， $v$ 和这条边所花费的时间 $w$ 。

接下来 $n$ 行，每行第一个整数 $k$ 表示 $i$ 号点有多少个时间点被限制了，接下来这一行紧接着 $k$ 个整数表示每个被限制的时间点 $t$ 。

输出一行一个整数表示答案。可以证明，答案一定存在。

对于 $50\%$ 的数据， $n \leq 100$ ， $k_{i} = 0$ ；
对于 $100\%$ 的数据， $1 \leq n \leq 500$ ， $1 \leq m \leq 1000$ ， $0 \leq k_{i} \leq 50$ ， $0 \leq t_{i} \leq 500$ ， $0 \leq w \leq 1000$ 。

保证对于同一个点，其被限制的时间 $t_{i}$ 互不相同。