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>.
# '''
# https://codeforces.com/contest/229/problem/B

# 输入 n(2≤n≤1e5) m(0≤m≤1e5) 表示一个 n 点 m 边的无向图（节点编号从 1 开始）。
# 然后输入 m 条边，每条边包含 3 个数 a b c(1≤c≤1e4)，表示有一条边权为 c 的无向边连接 a 和 b。
# 保证无自环、无重边。
# 然后输入 n 行，每行第一个数 k 表示数组 t[i] 的长度，然后输入数组 t[i]。
# 数组 t[i] 是一个严格递增序列，0≤t[i][j]<1e9。
# 所有 k 之和 ≤1e5。

# 初始时间为 0。你从 1 出发，要去 n。
# 如果你在点 i，但是当前时间在数组 t[i] 中，那么你必须等待 1 秒。如果下一秒仍然在 t[i] 中，那么继续等待 1 秒。依此类推。
# 输出到达 n 的最早时间。
# 如果无法到达 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
# '''
# from cmath import inf
# from collections import defaultdict
# from heapq import heappop, heappush


# def _n():
#     return int(input())


# def _nA():
#     return list(map(int, input().split()))


# def _nS():
#     return input().split()


# def solve():
#     n, m = _nA()
#     graph = [[]for _ in range(n)]
#     for i in range(m):
#         a, b, c = _nA()
#         a -= 1
#         b -= 1
#         graph[a].append((b, c))
#         graph[b].append((a, c))
#     t = [None]*n
#     for i in range(n):
#         t[i] = _nA()[1:]
#     dist = [inf]*n
#     dist[0] = 0
#     q = [(0, 0)]
#     while q:
#         d, x = heappop(q)
#         if d!=dist[x]:
#             continue
#         for i in t[x]:
#             if d == i:
#                 d += 1
#         for y, c in graph[x]:
#             if dist[x]+c < dist[y]:
#                 dist[y] = min(dist[y], d+c)
#                 heappush(q, (dist[y], y))
#     return dist[-1] if dist[-1] != inf else -1


# print(solve())

import sys
from heapq import *
r=sys.stdin.readline

n,m = map(int,r().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
    a,b,c=map(int,r().split())
    g[a].append((b,c))
    g[b].append((a,c))
times=[[]]
for _ in range(n):
    times.append(list(map(int,r().split()))[1:])

INF = sys.maxsize
dist = [INF]*(n+1)
dist[1]=0
q=[(0,1)]

while q:
    d,idx = heappop(q)
    if d !=dist[idx]:
        continue
    cur = dist[idx]
    for i in times[idx]:
        if i==cur:
            cur+=1
    for e,cost in g[idx]:
        if dist[e] > dist[idx]+cost:
            dist[e] = min(dist[e], cur+cost)
            heappush(q,(dist[e],e))
print(dist[n] if dist[n]!=INF else -1)
