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 re
import functools
import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
from bisect import bisect_right, bisect_left
BUFSIZE = 4096
inf = float('inf')
class SortedList:
    def __init__(self, iterable=[], _load=200):
        """Initialize sorted list instance."""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """Build a fenwick tree instance."""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """Update `fen_tree[index] += value`."""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """Return `sum(_fen_tree[:end])`."""
        if self._rebuild:
            self._fen_build()

        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """Return a pair of (the largest `idx` such that `sum(_fen_tree[:idx]) <= k`, `k - sum(_fen_tree[:idx])`)."""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return 0, k
        if k >= self._len - _list_lens[-1]:
            return len(_list_lens) - 1, k + _list_lens[-1] - self._len
        if self._rebuild:
            self._fen_build()

        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return idx + 1, k

    def _delete(self, pos, idx):
        """Delete value at the given `(pos, idx)`."""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens

        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1

        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """Return an index pair that corresponds to the first position of `value` in the sorted list."""
        if not self._len:
            return 0, 0

        _lists = self._lists
        _mins = self._mins

        lo, pos = -1, len(_lists) - 1
        while lo + 1 < pos:
            mi = (lo + pos) >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi

        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1

        _list = _lists[pos]
        lo, idx = -1, len(_list)
        while lo + 1 < idx:
            mi = (lo + idx) >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi

        return pos, idx

    def _loc_right(self, value):
        """Return an index pair that corresponds to the last position of `value` in the sorted list."""
        if not self._len:
            return 0, 0

        _lists = self._lists
        _mins = self._mins

        pos, hi = 0, len(_lists)
        while pos + 1 < hi:
            mi = (pos + hi) >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi

        _list = _lists[pos]
        lo, idx = -1, len(_list)
        while lo + 1 < idx:
            mi = (lo + idx) >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi

        return pos, idx

    def add(self, value):
        """Add `value` to sorted list."""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens

        self._len += 1
        if _lists:
            pos, idx = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """Remove `value` from sorted list if it is a member."""
        _lists = self._lists
        if _lists:
            pos, idx = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """Remove `value` from sorted list; `value` must be a member."""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """Remove and return value at `index` in sorted list."""
        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """Return the first index to insert `value` in the sorted list."""
        pos, idx = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """Return the last index to insert `value` in the sorted list."""
        pos, idx = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """Return number of occurrences of `value` in the sorted list."""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """Return the size of the sorted list."""
        return self._len

    def __getitem__(self, index):
        """Lookup value at `index` in sorted list."""
        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """Remove value at `index` from sorted list."""
        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """Return true if `value` is an element of the sorted list."""
        _lists = self._lists
        if _lists:
            pos, idx = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """Return an iterator over the sorted list."""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """Return a reverse iterator over the sorted list."""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """Return string representation of sorted list."""
        return 'SortedList({0})'.format(list(self))


class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
def I():
    return input()
 
def II():
    return int(input())
 
def MII():
    return map(int, input().split())
 
def LI():
    return list(input().split())
 
def LII():
    return list(map(int, input().split()))
 
def GMI():
    return map(lambda x: int(x) - 1, input().split())
 
def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))

def count_max(f, s):
    return min(f[0], s[1]) + min(f[1], s[2]) + min(f[2], s[0])

def get(lo, hi):
    return fol(hi) - fol(lo)

def fol(n):
    return n * (n + 1) * (2 * n + 1) // 6

def build_graph(parents):
    n = len(parents)
    ins = [0] * n
    for p in parents:
        if p != 0:
            ins[p - 1] += 1
    return ins
class UF:
    def __init__(self, n):
        self.ids = list(range(n))
        self.szs = [1] * n
        self.groups = n

    def union(self, i, j):
        fi, fj = self.find(i), self.find(j)
        if fi == fj:
            return
        ids = self.ids
        szs = self.szs
        self.groups -= 1
        si, sj = szs[fi], szs[fj]
        if si < sj:
            ids[fi] = fj
            szs[fj] += si
        else:
            ids[fj] = fi
            szs[fi] += sj

    def find(self, i):
        ids = self.ids
        while i != ids[i]:
            ids[i] = ids[ids[i]]
            i = ids[i]
        return i
    def get_groups(self):
        return self.groups

    def same_group(self, i, j):
        return self.find(i) == self.find(j)

    def union_groups(self):
        d = defaultdict(int)
        for i in range(len(self.ids)):
            p = self.find(i)
            d[p] += 1
        return list(d.values())

def hash(s):
    return (ord(s[0]) - ord('a') + 1) * 26 + ord(s[1]) - ord('a')
def is_even(a):
    return not a % 2

def build_graph(n):
    graph = [[] for _ in range(n)]
    edges = dict()
    for i in range(n - 1):
        u, v = LII()
        graph[u - 1].append(v - 1)
        graph[v - 1].append(u - 1)
        u -= 1
        v -= 1
        if u > v:
            u, v = v, u
        edges[(u, v)] = i + 1
    return graph, edges

def add(ans, u, v, edges):
    if u > v:
        u, v = v, u
    ans.append(edges[(u, v)])

def dfs(graph, edges, u, p, ans):
    total = 1
    for v in graph[u]:
        if v != p:
            size = dfs(graph, edges, v, u, ans)
            if size == -1:
                return -1
            if not size:
                add(ans, u, v, edges)
            total += size
    if total > 3:
        return -1
    if total == 3:
        return 0
    return total

def helper(arr):
    idx = len(arr) - 2
    while arr[idx] > arr[0]:
        idx -= 1
    return list(reversed(arr[idx+1:])) + arr[:idx+1]

M = int(1e9) + 7
N = int(2e5)
mods = [0] + [pow(i, -1, M) for i in range(1, N + 1)]

def build_graph(n, edges):
    graph = [dict() for _ in range(n)]
    for u, v, d in edges:
        graph[u][v] = graph[v][u] = d
    return graph

def dijstra(graph, src, dst):
    n = len(graph)
    dists = [inf] * n
    dists[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heappop(heap)
        if u == dst:
            return d
        if d <= dists[u]:
            for v, nd in graph[u].items():
                if nd and nd + d < dists[v]:
                    dists[v] = nd + d
                    heappush(heap, (dists[v], v))
    return inf

def mark(edges, idx, val):
    for i in range(idx, len(edges)):
        if not edges[i][2]:
            edges[i][2] = val

def print_arr(arr):
    print(" ".join(map(str, arr)))

def helper(s, n, ch, idx):
    while n > 0 and idx < len(s):
        if s[idx] == '*':
            s[idx] = ch
            n -= 1
        idx += 1
    return idx

def cnk(n, k):
    ans = 1
    for i in range(k):
        ans = (ans * n) % M
    return ans
def dijstra_change(graph, times, src, dst):
    n = len(graph)
    dists = [inf] * n
    dists[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heappop(heap)
        if u == dst:
            return d
        if d <= dists[u]:
            for v, nd in graph[u]:
                time = nd + d
                idx = bisect_right(times[v], (time, inf))
                if idx == 0:
                    pass
                else:
                    time = max(time, times[v][idx - 1][1] + 1)
                if time < dists[v]:
                    dists[v] = time
                    heappush(heap, (dists[v], v))
    return -1
def solve():
    n, m = LII()
    graph = [[] for _ in range(n)]
    for _ in range(m):
        u, v, c = LII()
        u, v = u - 1, v - 1
        graph[u].append((v, c))
        graph[v].append((u, c))
    times = []
    for _ in range(n):
        time = LII()
        k = len(time)
        lo = 0
        tt = []
        while lo < k:
            hi = lo + 1
            while hi < k and time[hi] == time[hi - 1] + 1:
                hi += 1
            tt.append((time[lo], time[hi - 1]))
            lo = hi
        times.append(tt)

    return dijstra_change(graph, times, 0, n - 1)


n = 1
for _ in range(n):
    print(solve())