1117: Query on a path

给出一个$N$个点的带权有向图，顶点编号为$1$到$N$，图中包括$N+M-1$条边，其中分两类边。

第一类边为$ \forall 1 \le i < N $，编号为$ i $的点连向编号为$ i+1 $的点，共$ N-1$条；

第二类边没有限制，共$M$条。

定义两点之间的最短路径为至多经过一次第二类边的路径中权值和最小的。现在有Q个询问，每次询问任意两点之间的最短路。

第一行两个数$N,M$，含义如题中所述。

第二行$N-1$个数，第$i$个表示$i$到$i+1$的第一类边的权值。

接下来$M$行，每行三个数$u,v,c$，表示$u$到$v$有一条边权为$c$的第二类边。

接下来一行一个数$Q$，再接下来$Q$行，每行两个数$u,v$，表示询问$u$到$v$的最短路。

输出共$Q$行，每行一个整数，表示每组询问的答案，数据保证路径存在且答案不超过$2^{31} - 1$ 。

对于30%的数据，$N \le 100, M \le 500$；

对于另外30%的数据，询问中作为起点的点不超过$5$个，且$N \le 1000, M \le 20000$；

对于另外30%的数据，询问中作为终点的点不超过$5$个，且$N \le 50000, M \le 200000$；

对于100%的数据，$N \le 100000, M \le 200000, q \le 200000$。

Time limit: 1000ms, memory limit: 50000kb.

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！