Note. The "$k$ paths" are not necessarily in the graph.

There is a weighted directed graph with $n$ vertices and $m$ edges (no multiple edges or self-loops). Given $k$ paths, find the shortest path from $1$ to $n$ (not necessarily a simple path) such that this path does not contain any of the given $k$ paths (containing means traversing the sequence of vertices of a given path consecutively). Output the length of this path, or $-1$ if no such path exists.

Input

The first line contains three integers $n, m, k$, representing the number of vertices, the number of edges, and the number of specified paths. The next $m$ lines each contain three integers $u_i, v_i, w_i$, representing a directed edge from $u_i$ to $v_i$ with weight $w_i$. The next $k$ lines each start with an integer $p$, representing the length of the given path, followed by $p$ integers describing the sequence of vertices in that path.

Output

Output a single integer representing the shortest length from $1$ to $n$ that does not contain any of the given paths. If no such path exists, output $-1$.

Examples

Input 1

7 8 2
1 2 1
2 3 2
3 4 1
4 5 1
4 6 1
5 7 1
6 7 1
6 5 2
6 1 2 3 4 5 7
5 2 3 4 6 7

Output 1

8

Input 2

4 4 2
1 2 1
2 3 1
3 4 1
3 2 1
4 1 2 3 4
6 1 2 3 2 3 4

Output 2

7

Subtasks

The path lengths below refer to the number of vertices in a path (counting repeated vertices multiple times).

• Subtask 1 ($20$ pts): $n, m \le 100, k = 0$;
• Subtask 2 ($20$ pts): $n, m \le 100$, each given path length is at most $4$;
• Subtask 3 ($30$ pts): $n, m \le 2 \times 10^5, k = 1$;
• Subtask 4 ($30$ pts): $n, m, k \le 2 \times 10^5$.

For all data, $1 \le n, m \le 2 \times 10^5, 0 \le k \le 2 \times 10^5, 1 \le u_i, v_i \le n, 0 \le w_i \le 10^9$, and the sum of the lengths of all given paths is at most $2 \times 10^5$.