题目描述

题目译自 XXVI Olimpiada Informatyczna – II etap Kolacje

Bajtek 和 Bajtyna 多年相恋，习惯在比特城温馨的餐厅共进浪漫晚餐。然而，作为保险代理人，他们工作到晚，常在不同城区结束一天，前往餐厅的路程耗时且费用不菲。

比特城规划完善，交通网络由 $n$ 个站点和 $n-1$ 条路线组成。每条路线连接两个站点，需单独购票。任意两站点间可通过直接或间接路线到达。

每个站点旁设有一家餐厅，擅长不同菜系（地中海风、东方风等），以编号 $1$ 至 $r$ 表示。

你的任务是编写程序，帮助 Bajtek 和 Bajtyna 选择聚餐地点，基于他们结束工作的站点和当晚想吃的菜系，计算最小的交通费用。

输入格式

第一行包含两个整数 $n, r$ $(2 \leq n \leq 100000, 1 \leq r \leq 100000)$，分别表示比特城的站点数和菜系种类。站点编号为 $1$ 至 $n$。

第二行包含 $n$ 个整数 $t_1, t_2, \ldots, t_n$ $(1 \leq t_i \leq r)$，表示站点 $i$ 旁餐厅的菜系种类。

接下来的 $n-1$ 行描述路线，第 $j$ 行包含三个整数 $a_j, b_j, c_j$ $(1 \leq a_j, b_j \leq n, a_j \neq b_j, 0 \leq c_j \leq 10^6)$，表示站点 $a_j$ 和 $b_j$ 间有路线，票价为 $c_j$。

下一行包含一个整数 $q$ $(1 \leq q \leq 100000)$，表示查询天数。

接下来的 $q$ 行描述查询，第 $k$ 行包含三个整数 $p_k, q_k, s_k$ $(1 \leq p_k, q_k \leq n, 1 \leq s_k \leq r)$，分别表示 Bajtek 结束工作的站点、Bajtyna 结束工作的站点及他们想吃的菜系。

输出格式

输出 $q$ 行，第 $k$ 行包含一个整数，表示第 $k$ 天满足要求的餐厅的最小交通费用。若无符合的餐厅，输出 $-1$。

5 4
1 2 3 1 3
1 2 3
2 3 4
2 4 5
3 5 0
4
1 3 3
1 4 2
1 5 1
3 3 4

7
8
7
-1

图中圆圈内数字为站点编号，粗体数字为餐厅菜系，边为路线，边上数字为票价。

• 第一天，两人想吃菜系 $3$ 的餐厅，位于站点 $3$ 和 $5$。Bajtek 和 Bajtyna 到这两站的总费用均为 $7$（Bajtek $7$，Bajtyna $0$）。
• 第二天，选择菜系 $2$ 的餐厅，仅在站点 $2$。总费用为 $3+5=8$。
• 第三天，想吃菜系 $1$ 的餐厅，位于站点 $1$ 和 $4$。到站点 $1$ 费用为 $0+7=7$，到站点 $4$ 为 $8+9=17$，故选 $7$。
• 第四天，比特城无菜系 $4$ 的餐厅，故输出 $-1$。

附加样例

1. $n=10, r=2$，站点随机连接，所有可能的查询。
2. $n=100$，站点 $i$ 的餐厅为菜系 $i$，每种菜系有 $2$ 个查询。
3. $n=10000$，站点依次连成线，所有餐厅为菜系 $1$，$10$ 个查询，第 $i$ 个查询站点 $i$ 和 $n$。

数据范围与提示

详细子任务附加限制及分值如下表所示。