题目描述

blg 一觉醒来发现穿越到了中世纪，blg 身无分文不得不去做任务去换取金钱用于填饱肚子。

现有 $n$ 个地点（编号从 $0$ 至 $n-1$，blg 初始位置为 0）有任务做，现有 $m$ 条无向路径连接各个地点，通过第 $i$ 条路径需要花费一定的时间 $t_i$。

除此之外在这神奇的大陆还有 $k$ 种不同的魔法道具（编号从$1\sim k$）分布在各个地方，blg 每到达一个地方，就可以收集到该地的魔法道具。如果拥有 $x$ 种不同的魔法道具则经过第 $i$ 条路径的时间仅需 $⌈t_i/2^x⌉$ (向上取整)。 由于 blg很饿了，希望你能告诉他分别到 $m$ 个任务地点的最短时间。如果无法到达某个地点，则输出-1。

输入格式

第一行是三个整数 $n$、$m$ 和 $k$。

接下来 $m$ 行，每行 3 个数字 $u_i,v_i,t_i$，表示 $u_i$ 和 $v_i$之间有一条路，通过需要 $t_i$ 时间。

接下来 $1$ 行，有 $n-1$ 个数字，第 $i$ 个数字表示在位置 $i$ 有一个编号为 $x_i(0≤x_i≤k)$ 的魔法道具（这意味着 blg 的出发点没有魔法道具）。注意，魔法道具编号是 $1\sim k$，如果 $x_i=0$ 说明该处没有魔法道具。

输出格式

输出 $n-1$ 行，依次表示到所有任务点的最短时间。如果无法到达该地点，输出 -1。

测试样例

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

5
3
4

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

3
-1
2

6 6 2
0 1 8
2 1 7
2 3 7
4 3 7
0 5 7
4 5 7
1 2 2 2 2

8
12
14
11
7

样例说明

样例1中：

0->1：距离为5；0->2：距离为3；0->2->3：距离为4。

样例3中，关于点3：

0->1->2->3：距离为8+4+2=14；0->5->4->3：距离为7+4+4=15。

数据规模说明

对 $30\%$ 的数据，$2≤n≤20$，$1≤m≤50$ 且 $k=0$。

对 $100\%$ 的数据，$2≤n≤5000$，$1≤m≤100000$ ，$0≤k≤10$ 且 $1≤t_i≤400000)$。