年度 CCPC（Cipher & Code Penetrating Competition）即将到来，今年的比赛采用了一种独特的题目解锁方式。

本次比赛共有 $n$ 道题目，编号为 $1$ 到 $n$。然而，与往年不同的是，今年的题目并非在比赛开始时全部解锁，而是逐步解锁。具体来说，组委会根据题目之间的关系确定了一个包含 $n$ 个节点的有向图，其中节点 $1$ 到 $n$ 分别代表第 $1$ 到第 $n$ 道题目。初始时，每道题目的能量等级均为 $0$，且每道题目都有一个参数 $a_i$，表示如果该题目的能量等级大于或等于 $a_i$，则该题目会立即解锁。一旦解锁，所有从该节点出发的有向边将同时向对应的目标题目传输 $1$ 点能量，传输过程需要 $w$ 秒。

然而，组委会发现有些题目可能永远无法解锁，这是他们希望避免的情况。因此，他们设计了 $k$ 个强制刷新器来帮助参赛者推进进度。每个强制刷新器控制若干题目，并会在 $t_j$ 秒时被激活，立即将其控制的所有题目的参数 $a_i$ 修改为 $0$。

现在，对于每一道题目，你需要求出其最早解锁时间，或者判断它是否永远无法解锁。

输入格式

第一行包含三个整数 $n, m, k$ ($3 \le n \le 10^5, 0 \le m \le 10^6, 0 \le k \le 10^5$)，分别表示题目数量、有向边数量和强制刷新器数量。

第二行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 10^5$)，表示每道题目的参数。保证至少存在一个 $i$ 使得 $a_i = 0$。

接下来的 $k$ 行，第 $j$ 行包含两个整数 $t_j, sc_j$ ($0 \le t_j \le 10^9, 1 \le sc_j \le n$)，表示第 $j$ 个强制刷新器在 $t_j$ 秒时激活并控制 $sc_j$ 道题目，随后是 $sc_j$ 个整数 $id_1, \dots, id_{sc_j}$ ($1 \le id_l \le n$)，表示该强制刷新器控制的题目编号。保证同一个强制刷新器控制的题目编号互不相同。

接下来的 $m$ 行，每行包含三个整数 $u, v, w$ ($1 \le u, v \le n, 0 \le w \le 10^9, u \neq v$)，表示存在一条从题目 $u$ 到题目 $v$ 的有向边，传输 $1$ 点能量需要 $w$ 秒。

保证 $\sum sc_i \le 10^6$。

输出格式

输出一行包含 $n$ 个整数，表示每道题目解锁所需的最短时间。如果某道题目永远无法解锁，则输出 $-1$。

样例

样例输入 1

6 9 0
0 2 1 1 1 4
1 2 1
2 3 1
3 4 1
4 5 1
5 2 1
2 6 1
3 6 1
4 6 1
5 6 1

样例输出 1

0 -1 -1 -1 -1 -1

样例输入 2

6 9 1
0 2 1 1 1 4
100 2 3 5
1 2 1
2 3 1
3 4 1
4 5 1
5 2 1
2 6 1
3 6 1
4 6 1
5 6 1

样例输出 2

0 101 100 101 100 102

样例输入 3

4 3 0
1 0 1 1
3 1 10
1 2 100
2 4 1000

样例输出 3

-1 0 -1 1000

说明

注意：本题输入规模较大，请使用较快的输入方法进行读取。