### 问题描述 小X同志在出题，有很多知识点供她选择，每个知识点有难度等级，可能存在若干个知识点具有相同的难度等级。每个题目要求了必须使用的某两个知识点 $a_i$ 和 $b_i$，其他知识点可用可不用，并且规定了除去知识点 $a_i$ 和 $b_i$，该题目使用的其他知识点难度不能超过 $k_i$。 小X出题的思路是由第一个知识点联想到第二个，再由第二个联想到第三个，直至最后一个，并且小X想把题目要求的两个知识点分别作为题目的第一个和最后一个知识点，中间的知识点视情况发挥。从一个知识点联想到另外一个知识点需要时间。对于小X而言，从知识点 $x$ 联想到知识点 $y$ 和从知识点 $y$ 联想到知识点 $x$ 所需要的时间是一样的。 现在有若干道题目要求，小X想知道每道题目的最短出题时间。 ### 输入格式 输入第一行包含两个整数 $N,M,P$，分别表示知识点个数、可以直接联想的知识点关系个数、题目个数。 第二行包含 $N$ 个整数，其中第 $x$ 个数字 $D_x$ 表示第 $x$ 个知识点的难度。 接下来 $M$ 行，每行三个整数 $u,v,w$，表示从知识点 $x$ 联想到知识点 $y$ 所需要的时间为 $w$。 接下来 $P$ 行，每行三个数字 $a_i,b_i,k_i$，分别表示必须使用的两个知识点和难度限制。 ### 输出格式 输出 $P$ 行，每行一个整数，表示答案。 如果某题目在难度限制下不能完成出题，请输出 $-1$。 ### 样例输入 ```text 5 4 3 5 3 7 2 1 1 2 2 2 3 3 2 4 1 2 5 4 1 5 2 1 5 3 4 5 8 ``` ### 样例输出 ```text -1 6 5 ``` ### 说明 对于 $30$% 的评测数据，$1\leq P\leq 10$。 对于 $60$% 的评测数据，$1\leq P\leq 10^4$。 对于 $100$% 的评测数据，$1\leq N\leq 200$，$1\leq M\leq N\times N\div 2$，$1\leq P\leq 10^6$，$1\leq D_x,k_i\leq 10^7$，$1\leq w\leq 10^6$，$a_i\neq b_i$。在给出的知识点联想关系中，保证一对可以直接联想的知识点只会出现一次，保证所有知识点都可以直接或者间接联想到且 $u\neq v$。