### 问题描述 根据沃兹基硕德先生的十八线小道消息，盗月社的蒜香百灵鸟为庆祝复出打算前往多个城市与重要地方特色文化象征进行会晤，为了节省资金他们购买了百亿补贴勋多多航空公司的年卡，年卡能给他们提供免费的航班，但可惜的是，不是所有航班都免费，仍然有许多航班需要原价购买飞机票，所以他们迫切寻找一个聪明绝顶的算法带师，帮他们计算从城市 $ 1$ 飞往任意一个城市最少需要多少钱。 ### 输入格式 输入第 $1$ 行包含一个正整数 $T(1≤T≤10)$，表示测试数据的组数。 每组测试数据的第 $1$ 行是三个正整数 $n，m，k(1< n \leq 2\times 10^5，1< m+k \leq 2\times 10^5)$。 接下来 $m$ 行，每行包含两个正整数 $x，y$，表示从城市 $x$ 飞往城市 $y$ 的航班是免费的 $(x\neq y$ 并且 $1< x,y \leq n)$。 最后 $k$ 行，每行包含三个正整数 $x，y，z$，表示从城市 $x$ 飞往城市 $y$ 的航班价格为 $z(x\neq y$ 并且 $1< x,y \leq n,1\leq z \leq 10^9)$。 ### 输出格式 每组样例输出一行，这一行只包含一个整数，表示答案。 ### 样例输入1 ```text 1 10 4 6 8 10 5 9 6 7 10 7 9 1 9 9 7 2 1 8 8 1 5 4 5 8 5 8 9 4 ``` ### 样例输出1 ```text 0 -1 -1 -1 4 -1 6 8 4 8 ``` ### 样例输入2 ```text 3 12 15 1 1 2 2 8 7 8 9 8 3 12 6 8 6 5 12 3 2 11 7 12 8 5 5 10 2 4 11 8 4 5 6 1 1 6 7 4 3 4 1 5 4 2 5 6 1 6 5 3 1 2 5 2 6 3 2 2 4 6 1 3 5 7 7 15 3 1 5 3 2 4 1 6 2 7 2 5 3 3 7 7 5 3 6 4 2 5 2 2 7 1 3 2 1 4 7 7 3 10 6 3 2 6 4 7 ``` ### 样例输出2 ```text 0 0 -1 0 0 -1 -1 0 -1 0 0 -1 0 0 0 0 0 0 0 0 0 7 0 0 0 ```