Ostania 是一个由 $n$ 个城市和 $m$ 条单向道路组成的国家。城市编号从 $1$ 到 $n$，第 $i$ 条道路（$1 \le i \le m$）是从城市 $u_i$ 到城市 $v_i$ 的单向道路。通过第 $i$ 条道路需要 $w_i$ 单位时间。对于任意两个不同的城市 $u$ 和 $v$，从 $u$ 到 $v$ 最多只有一条道路。为方便起见，记 $w(u, v)$ 为通过相应道路从城市 $u$ 到城市 $v$ 所需的时间。

Westalis 是一个与 Ostania 处于冷战关系的国家。Westalis 通过各种间谍获得了关于 Ostania 的 $k$ 条情报。每条情报都表示为一条简单路径。具体来说，第 $j$ 条情报（$1 \le j \le k$）由一个包含 $s_j$ 个不同城市的序列 $(p_{j,1}, p_{j,2}, \dots, p_{j,s_j})$ 组成，其中对于 $1 \le t < s_j$，存在一条从城市 $p_{j,t}$ 到城市 $p_{j,t+1}$ 的道路。没有任何城市同时属于多于一条情报。

Westalis 的代号为“黄昏”（Twilight）的间谍目前位于 Ostania 的城市 $1$。Westalis 政府指示“黄昏”前往城市 $x$。为了最大限度地提高情报收集的效率，“黄昏”决定走一条不包含任何已知 $k$ 条简单路径的路径。具体来说，设“黄昏”访问的城市序列为 $(q_1, q_2, \dots, q_\ell)$。必须满足以下所有条件：

1. 对于 $1 \le i < \ell$，存在一条从城市 $q_i$ 到城市 $q_{i+1}$ 的道路。
2. 不存在整数 $i$ 和 $z$ 使得 $(p_{z,1}, p_{z,2}, \dots, p_{z,s_z}) = (q_i, q_{i+1}, \dots, q_{i+s_z-1})$。
3. 在满足条件 $1$ 和 $2$ 的前提下，使“黄昏”到达城市 $x$ 所需的时间 $\sum_{i=1}^{\ell-1} w(q_i, q_{i+1})$ 最小化。

你需要确定对于从 $1$ 到 $n$ 的每个 $x$，“黄昏”是否能从城市 $1$ 到达城市 $x$，如果可以，计算所需的时间。

输入格式

第一行包含三个整数：$n, m$ 和 $k$（$2 \le n \le 2 \cdot 10^5$；$1 \le m \le 3 \cdot 10^5$；$0 \le k \le \frac{n}{2}$）。

接下来的 $m$ 行描述道路。第 $i$ 行包含三个整数：$u_i, v_i$ 和 $w_i$（$1 \le u_i, v_i \le n$；$1 \le w_i \le 10^9$；$u_i \neq v_i$）。对于任意两个不同的城市 $u$ 和 $v$，从 $u$ 到 $v$ 最多只有一条道路。

接下来的 $k$ 行描述路径。第 $j$ 行以一个整数 $s_j$ 开头，表示路径长度，随后是 $s_j$ 个整数 $p_{j,1}, \dots, p_{j,s_j}$：即路径本身（$s_j \ge 2$；$\sum_{j=1}^k s_j \le n$）。在所有给定的路径中，每个城市最多出现一次。保证道路可以按给定的顺序遍历。

输出格式

输出一行，包含 $n$ 个整数：在给定条件下“黄昏”到达城市 $1, 2, \dots, n$ 所需的时间。如果某个城市无法到达，则输出 $-1$。

样例

样例输入 1

4 4 1
1 2 2
1 3 1
2 4 2
3 4 5
2 2 4

样例输出 1

0 2 1 6

样例输入 2

4 4 2
1 2 2
1 3 1
2 4 2
3 4 5
2 1 3
2 2 4

样例输出 2

0 2 -1 -1

样例输入 3

11 12 3
1 2 40
2 3 40
3 1 40
2 4 20
3 6 10
9 1 1
10 11 1
3 7 1
7 6 2
6 7 3
7 8 4
4 5 3
4 1 2 4 5
3 3 7 8
2 10 11

样例输出 3

0 40 80 60 -1 83 81 90 -1 -1 -1