M. 门不能从这一侧打开
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

在小 C 的世界里，有 n 个藏宝点，m 条连接藏宝点的双向道路，每条道路都有其特定的长度 l。

这个世界受到了神奇的诅咒，阻止所有贪婪的寻宝人：有 k 个限制 (x, y, z) 表示从藏宝点 x 走到藏宝点 y 后不能往藏宝点 z 走。注意三元组是有序的，如可以从藏宝点 y 走到藏宝点 x 再走到藏宝点 z。

形式化地，如果小 C 从藏宝点 1 到藏宝点 T 所经过的藏宝点序列为 (u0 = 1, u1, ..., up = T)，则该序列的任意一个长度为 3 的连续子序列 (ui - 1, ui, ui + 1) 不能跟 k 个限制中的任意一个表示的三元组 (xj, yj, zj) 完全相同。两个三元组 (a, b, c) 和 (x, y, z) 完全相同当且仅当 a = x 且 b = y 且 c = z。

但是小 C 不仅贪婪而且有人脉，他想请你帮他分别计算出从藏宝点 1 出发，到达藏宝点 1, 2, ..., n 所需的最短路径长度。

Input

第一行输入三个正整数 n, m, k (1 ≤ n, m, k ≤ 5 × 105)，分别表示藏宝点个数，道路个数，限制个数。

接下来 m 行，每行输入三个正整数 u, v, l (1 ≤ u, v ≤ n, 1 ≤ l ≤ 109)，表示有一条连接 u 和 v 长度为 l 的道路。不保证 u ≠ v，但保证对于任意第 i 行和第 j 行 (i ≠ j) 输入的边 (ui, vi) 和 (uj, vj)，不存在 () 或 ()，即任意两点之间至多有一条直接相连的道路。

接下来 k 行，每行输入三个正整数 x, y, z (1 ≤ x, y, z ≤ n)，表示一个限制。

Output

输出 n 行。

第 i 行输出一个正整数或  - 1 。如果能从藏宝点 1 走到藏宝点 i，则输出最短路径长度；如果无法到达，则输出  - 1。

Example
Input
3 2 1
1 2 114514
2 3 1919810
1 2 3
Output
0
114514
-1