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*.
The first line contains two space-separated integers: *n* (2 ≤ *n* ≤ 10<sup class="upper-index">5</sup>), the number of planets in the galaxy, and *m* (0 ≤ *m* ≤ 10<sup class="upper-index">5</sup>) — 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*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ *n*, *a*<sub class="lower-index">*i*</sub> ≠ *b*<sub class="lower-index">*i*</sub>), which are connected through stargates, and the integer transfer time (in seconds) *c*<sub class="lower-index">*i*</sub> (1 ≤ *c*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">4</sup>) 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*<sub class="lower-index">*i*</sub> (0 ≤ *k*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>) that denotes the number of moments of time when other travellers arrive to the planet with index *i*. Then *k*<sub class="lower-index">*i*</sub> distinct space-separated integers *t*<sub class="lower-index">*ij*</sub> (0 ≤ *t*<sub class="lower-index">*ij*</sub> &lt; 10<sup class="upper-index">9</sup>) follow, sorted in ascending order. An integer *t*<sub class="lower-index">*ij*</sub> means that at time *t*<sub class="lower-index">*ij*</sub> (in seconds) another traveller arrives to the planet *i*. It is guaranteed that the sum of all *k*<sub class="lower-index">*i*</sub> does not exceed 10<sup class="upper-index">5</sup>.
import heapq
import random
import sys
from collections import defaultdict
from math import inf
from types import GeneratorType

RANDOM = random.randint(1, 10 ** 9)


class FastIO:
    def __init__(self):
        return

    @staticmethod
    def read_str():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def read_int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def read_float():
        return float(sys.stdin.readline().rstrip())

    @staticmethod
    def read_ints():
        return map(int, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_floats():
        return map(float, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_ints_minus_one():
        return map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_list_ints():
        return list(map(int, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_floats():
        return list(map(float, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_ints_minus_one():
        return list(map(lambda x: int(x) - 1,
                        sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_strs():
        return sys.stdin.readline().rstrip().split()

    @staticmethod
    def read_list_str():
        return list(sys.stdin.readline().rstrip())

    @staticmethod
    def st(x):
        return print(x)

    @staticmethod
    def lst(x):
        return print(*x)

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def bootstrap(f, queue=[]):
        def wrappedfunc(*args, **kwargs):
            if queue:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if isinstance(to, GeneratorType):
                        queue.append(to)
                        to = next(to)
                    else:
                        queue.pop()
                        if not queue:
                            break
                        to = queue[-1].send(to)
                return to

        return wrappedfunc

    def ask(self, lst):
        self.lst(lst)
        sys.stdout.flush()
        res = self.read_int()
        return res

    @staticmethod
    def accumulate(nums):
        n = len(nums)
        pre = [0] * (n + 1)
        for i in range(n):
            pre[i + 1] = pre[i] + nums[i]
        return pre


class Wrapper(int):
    # 用来规避 py 哈希碰撞的问题和进行加速
    def __init__(self, x):
        int.__init__(x)
        # 原理是异或一个随机种子

    def __hash__(self):
        # 也可以将数组排序后进行哈希计数
        return super(Wrapper, self).__hash__() ^ RANDOM


class UnionFind:
    def __init__(self, n: int) -> None:
        self.root = [i for i in range(n)]
        self.size = [1] * n
        self.part = n
        return

    def find(self, x):
        lst = []
        while x != self.root[x]:
            lst.append(x)
            # 在查询的时候合并到顺带直接根节点
            x = self.root[x]
        for w in lst:
            self.root[w] = x
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.size[root_x] >= self.size[root_y]:
            root_x, root_y = root_y, root_x
        self.root[root_x] = root_y
        self.size[root_y] += self.size[root_x]
        # 将非根节点的秩赋0
        self.size[root_x] = 0
        self.part -= 1
        return True

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

    def get_root_part(self):
        # 获取每个根节点对应的组
        part = defaultdict(list)
        n = len(self.root)
        for i in range(n):
            part[self.find(i)].append(i)
        return part

    def get_root_size(self):
        # 获取每个根节点对应的组大小
        size = defaultdict(int)
        n = len(self.root)
        for i in range(n):
            size[self.find(i)] = self.size[self.find(i)]
        return size


class Solution:
    def __init__(self):
        return

    @staticmethod
    def main(ac=FastIO()):
        n, m = ac.read_ints()
        dct = [[] for _ in range(n)]
        for _ in range(m):
            a, b, c = ac.read_ints_minus_one()
            dct[a].append([b, c + 1])
            dct[b].append([a, c + 1])

        post = []
        for _ in range(n):
            cur = ac.read_list_ints()[1:]
            tmp = dict()
            for num in sorted(cur, reverse=True):
                tmp[num] = tmp.get(num + 1, num + 1)
            post.append(tmp)

        dis = [inf] * n
        stack = [[0, 0]]
        dis[0] = 0

        while stack:
            d, i = heapq.heappop(stack)
            if dis[i] < d:
                continue
            dd = post[i].get(d, d)
            for j, w in dct[i]:
                dj = w + dd
                if dj < dis[j]:
                    dis[j] = dj
                    heapq.heappush(stack, [dj, j])
        ac.st(dis[-1] if dis[-1] < inf else -1)
        return


Solution().main()
