图论SPFA

Description

给定一个有向图点数为$n(n \le 2000)$，边数为$m(m \le 100000)$，边上带权，有$q$组询问，每个询问给出一个$dt(0 \lt dt \le 300000)$，要求对于每个询问，将图中所有边的边权都加上$dt$后，从$S$到$T$的最短路(数据保证一定存在从$S$到$T$的路径)。

Input

第一行为数据组数$TT(TT \le 25)$。每组数据的第一行为三个整数$n,m,q$,含义如题所述。接下来$m$行每行三个整数$x(1 \le x \le n),y(1 \le y \le n),c(1 \le c \le 300000)$,代表一条从$x$到$y$的权值为$c$的边。接着一行为$S$和$T$(保证$S \neq T$)。接下来的$q$行每行一个正整数$dt$,代表$dt$的询问。数据中可能出现重边和自环。

Output

每组数据输出$q$行，第$i$行为该组数据第$i$个询问的答案。

Sample Input

1
6 7 3
1 3 1
1 2 2
2 5 3
3 4 2
3 5 4
4 5 1
5 6 1
1 6
1
2
3

Sample Output

9
12
15

Source

Awcrr