题目描述Description

一年一赛季的 CCPC（Cipher & Code Penetrating Competition）即将来临，今年的比赛采取了与众不同的方式来进行题目的发放。

本次比赛共有 n 道题目，编号从 1 到 n。但与往年不同的是，今年的题目并不是比赛一开始就全部解锁的，而是逐步解锁的。具体来说，组委会根据题目之间的关系确定了一张具有 n 个点的有向图，节点编号从 1 到 n，点 i 代表第 i 道题。最初每道题具有的能量都为 0，并且每道题目都有一个参数 a_i，表示如果这道题具有的能量大于等于 a_i，这道题就会被立刻解锁。当其解锁后，从该点出发的所有有向边将会同时向该边对应的终点题目传输 1 点能量，传输需要花费 w_i 的时间。

但组委会发现有些题目可能永远无法被解锁，这是组委会不想看到的，因此组委会设计了 k 个强制刷新器来帮助选手推进进度。每个强制刷新器管控一些题目，并且会在第 t_i 秒被启动，其启动后会立刻将其管控的题目的参数 a_i 修改为 0。

现在对于每个题目，你想知道其最早的解锁时间，或者判断其永远无法被解锁。

输入格式Input

第一行三个整数 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,\ldots,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 有一条有向边，其需要 w 的时间传输 1 点能量。

数据保证 \sum sc_i \le 10^6。

输出格式Output

输出一行共 n 个整数，表示解锁这个题目所需要的最短时间，如果这道题目永远无法被解锁，则输出 -1。

样例Sample

提示Hint

注意本题数据输入量过大，请采用较快的输入方法进行读入

出题Author

来源Source