说粗来泥萌可能不信，Home_W喜欢的公主被魔王抓走了！！！
Home_W当然是要去救公主的，但是魔塔的结构很复杂，Home_W需要聪明的你帮助他，找到一条最省魔力的路径去打到魔王，拯救公主。
魔塔有n个传送阵，编号从1-n，而且魔塔有很多层，最多不超过n层，编号从1-n。
任意相连的两层里的传送阵都可以互相传送（比如第二层有传送阵 1 2，第三层有传送阵 3 4 ，那么 1-3，1-4，2-3，2-4都可以互相传送，这些传送费用都为C）
传送当然需要消耗魔力了，相连两层之间传送消耗的魔力 为C，另外Home_W还得知，有额外的m条传送通道（双向）
Home_W初始位置为编号为1的传送阵，魔王在编号为n的传送阵上。
输入第一行一个T表示T组测试数据
第一行三个数n,m（0<=n,m<=1e5），c(1<=c<=1e3) n个传送阵，m个额外的传送通道，相连两层之前传送花费为c
接下来一行n个数a1-an,表示第i个传送阵在ai层
接下来m行，每行三个数u,v,w 表示从传送阵u传送到v需要花费w的魔力 (1<=w<=1e4)
对于第i组样例输出
Case #i: ans
ans为消耗的最小魔力，不存在输出-1
2 3 3 3 1 3 2 1 2 1 2 3 1 1 3 3 3 3 3 1 3 2 1 2 2 2 3 2 1 3 4
Case #1: 2 Case #2: 3 第一个样例：传送阵1 - 2 花费为1 传送阵2 - 3 花费为1 传送阵1 - 3 花费为3 第一层到第二层 互相传送的传送阵 1 - 3 花费为 3 第二层到第三层 互相传送的传送阵 3 - 2 花费为 3 答案是 1-2-3 花费为2