题目描述

每年春季，在某岛屿上都会举行游行活动。

在这个岛屿上有 $N$ 个城市，$M$ 条连接着城市的有向道路。

你要安排英雄们的巡游。英雄从城市 $s_i$ 出发，经过若干个城市，到城市 $t_i$ 结束，需要特别注意的是，每个英雄的巡游的 $s_i$ 可以和 $t_i$ 相同，但是必须至少途径 $2$ 个城市。 每次游行你的花费将由 $3$ 部分构成：

1. 每个英雄游行经过的距离之和，需要特别注意的是，假如一条边被途径了 $k$ 次，那么它对答案的贡献是 $k\times c_i$，$c_i$表示这条边的边权。
2. 如果一个英雄的巡游的 $s_i$ 不等于 $t_i$，那么会额外增加 $C$ 的费用。因为英雄要打的回到起点。
3. 如果一个城市没有任何一个英雄途经，那么这个城市会很不高兴，需要 $C$ 费用的补偿。

你有无数个的英雄。你要合理安排游行方案，使得费用最小。

由于每年，$C$ 值都是不一样的。所以你要回答 $Q$ 个询问，每个询问都是，当 $C$ 为当前输入数值的时候的答案。

输入格式

第一行正整数 $N,M,Q$；

接下来的 $M$ 行，每行 $a_i,b_i,c_i$，表示有一条从 $a_i$ 到 $b_i$，边权为 $c_i$ 的有向道路。保证不会有自环，但不保证没有重边。

接下来 $Q$ 行，每行一个 $C$，表示询问当每次费用为 $C$ 时的最小答案。

输出格式

$Q$ 行，每行代表一个询问的答案。

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

6
21
32

数据规模与约定

对于 $100\%$ 的数据，$2\le N\le 250,1\le M\le 30000,1\le Q\le 10000,1\le ci\le 10000,1\le C\le 10000$。

提示

第一年的时候，$C$ 只有 $1$。我们比较懒所以就不安排英雄出游了，需要支付 $6$ 的费用。

第二年的时候，我们可以这么安排：第一个英雄 $1\to 3\to 4\to 5$，需要付 $2+2+2=6$ 的费用，同时还要花 $5$ 费用打的回家。再花 $5+5$ 的费用来补偿 $2$ 号城市和 $6$ 号城市。

第三年略。