410707: GYM104081 H 提瓦特之旅

熠熠星辰闪耀天际

旅程中的每一次相逢

都将被细细镌刻在

旅者传颂的歌谣中

YahAHa 准备和 ColdHeat 一起遨游提瓦特大陆。提瓦特大陆可以视为 $$$n$$$ 个点 $$$m$$$ 条边的无向连通图，如果 $$$u$$$ 和 $$$v$$$ 之前存在一条无向边，则从 $$$u$$$ 到 $$$v$$$ 或者从 $$$v$$$ 到 $$$u$$$ 需要的时间为 $$$c_{uv}$$$ 。

刚开始 YahAHa 位于 $$$1$$$ 号节点，ColdHeat 位于 $$$t$$$ 号节点。YahAHa 想要尽快赶到 ColdHeat 身边，不过 YahAHa 经过的每一个节点都有可能刷新委托。为了帮 ColdHeat 抽到喜欢的角色 YahAHa 会顺手解决他们并获取原石，经过路上的第 $$$i$$$ 个点时 YahAHa 需要 $$$w_i$$$ 的时间完成委托，最多一共刷新 $$$n-1$$$ 个委托。现在 YahAHa 想知道他最短需要多少时间找到 ColdHeat。

换而言之，一共有 $$$q$$$ 次询问，每次询问给出 $$$t,w_1,w_2,...,w_{n-1}$$$ $$$(t \neq 1)$$$ ，询问从 $$$1$$$ 到 $$$t$$$ 所需的最短时间。如果当前的路径经过了 $$$k+1$$$ 个节点，分别为 $$$u_0=1,u_1,u_2,..,u_k=t$$$ ，则 YahAHa 所需额外的时间为 $$$w_1+w_2+...+w_k$$$。

第一行给定两个整数 $$$n,m$$$ $$$(1 \le n \le 500, 1 \le m \le 10^5)$$$ 。

第二行开始 $$$m$$$ 行，每行三个整数 $$$u, v, c_{uv}$$$ $$$(1 \le c_{uv} \le 10^9)$$$。

第 $$$m+2$$$ 行给定一个整数 $$$q$$$ $$$(1 \le q \le 5000)$$$ 。

然后开始 $$$q$$$ 行，每次询问给出 $$$n$$$ 个整数 $$$t,w_1,w_2,...,w_{n-1}$$$ $$$(2 \le t \le n, 0 \le w_i \le 10^9)$$$ 。

$$$q$$$ 行，每行一个整数表示答案。

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

2
3