Note. 「$k$ 条路径」不一定在图中。

题目描述

有一张 $n$ 个点，$m$ 条边的带权有向图（无重边、自环），再给定 $k$ 条路径，求一条 $1$ 到 $n$ 的最短路径（不要求是简单路径），使得这条路径不包含给定 $k$ 条路径中的任何一条（包含指连续地经过某条路径）。输出此路径的长度，如果找不到输出 $-1$。

输入格式

第一行输入三个整数 $n, m, k$，表示图的点数、边数和钦定路径条数。 接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$ 表示有一条从 $u_i$ 到 $v_i$，边权为 $w_i$ 的有向边。 接下来 $k$ 行，每行先输入一个整数 $p$，表示这条给定路径的长度，后面有 $p$ 个整数，描述了这条给定的路径。

输出格式

输出一行一个整数表示从 $1$ 到 $n$ 不经过给定路径的最短长度。如果不存在输出 $-1$。

样例一

input

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

8

样例二

input

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

7

子任务

以下的路径长度均指一条路径经过的点个数（重复点算多次）。

• Subtask1($\text{20 pts}$)：$n, m \le 100, k = 0$；
• Subtask2($\text{20 pts}$)：$n, m \le 100$，每条给定路径长度不超过 $4$；
• Subtask3($\text{30 pts}$)：$n, m \le 2 \times 10^5, k = 1$；
• Subtask4($\text{30 pts}$)：$n, m, k \le 2 \times 10^5$。

对于所有数据，有 $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$，路径长度总和小于等于 $2 \times 10^5$。