分层图最短路
题号：NC236176
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给一张 n 个点的无向图，其中每一个点都在某一层 l_i 内，对于不同的层，我们还可以花费 C 的代价从层 x 的某一个点到达层  的某一个点（如果层  没有点，则不能进行此操作），当然也可以从层  的某一点花费 C 的代价到达层 x 的某一点（如果层 x 没有点，则不能进行此操作）。此外，还有 m 条特殊的双向边，每条边连接两个不同的点 u_i,v_i ，走这条边的花费是 w_i 。
你需要求出从1号点到达 n 号点的最小花费。注意：如果点 u,v 在同一层，且 u,v 之间没有连边，那么你不能从 u 花费 0 的代价直接到 v 。

输入描述:

第一行输入三个整数  ，分别表示点数、边数和在两个相邻层之间的移动花费。
接下来一行输入 n 个整数  ，分别表示每个点所在的层。
接下来 m 行，每行输入三个整数  ，描述额外的 m 条双向边。

输出描述:

输出一行一个整数，表示从节点1到节点n的最小花费。如果你不能从1到达 n ，则输出-1。
示例1

输入

复制 
4 3 3
1 2 2 3
1 4 1000
1 2 10
1 3 2

输出

复制 
5
示例2

输入

复制 
3 1 3
1 3 3
1 2 4

输出

复制 
-1