3030: 中国特色社会路

小W非常喜欢社会主义，这天他开始研究它的优越性。

他发现它们国家十分乐于修建特色的社会主义道路。具体的说，Z国有n座城市，由m条有向边连接，城市从1编号。

特色的地方在于，时不时会有一些LD下来在城市间视察，视察时他会从城市 b_i 开始，最终到 e_i 结束。每次视察都会走过一些路，这些路自然会被LD所注意。

更具体地，LD会重修自己走过的路。每条边重修需要的费用也不相同。

而如果视察结束后，LD不在一开始自己所在的城市bi，则会要新建一条VIP道路送他回家，也就是只有他自己能通过的道路。这需要花费固定的费用C，这条道路走过后便会拆毁。

若某个城市没有被LD经过，则这个城市的下级LD会被勒令整改，也要花费C的费用。

现在有k年，每年有若干个LD下来视察(可能0个)，每年的固定费用C不同。小W想知道对于每一年怎样安排他们的视察人数和视察路线，能使得总花费最小。注意领导至少要视察一条边。

注意，若一条道路被同一个人多次经过，则每次都会重修这条路。多个 人多次经过也是一样。没有被LD经过的城市，更具体的说是没有被任何LD经过

第一行三个整数 n, m, k。接下来m行每行三个整数 s_i, t_i, v_i，表示 s_i 和 t_i 间的有向边，重修需要花费 v_i 的代价。接下来 k 行每行一个整数，表示这一年的固定费用 C。

输出k行，每行一个最小花费。

6 5 3
1 3 2
2 3 2
3 4 2
4 5 2
4 6 2
1
5
10

6
21
32