简单图论题

题号：NC312108
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 有一个 $n$ 个点 $m$ 条边构成的无向图 $G$ ，第 $i$ 条边 $(u_i,v_i)$ 有一个颜色 $c_i$ 。现在有一个环形颜色圆盘，其包含了编号 $[0,P-1]$ 的颜色，圆盘上有一个指针，初始指向颜色 $0$ ，若指针指向颜色 $x$ ，则可以花费 $1$ 的代价将其指向 $\left(x+P-1\right)\bmod P$ 或 $\left(x+1\right)\bmod P$ 。
$\hspace{15pt}$ 第 $i$ 个点有一个颜色偏转值 $b_i$ 。当你想走过边 $(u,v,c)$ 时：
$\hspace{23pt}\bullet\,$ 若从点 $u$ 走向点 $v$ ，那你在点 $u$ 时圆盘的指针必须指向 $\left(c+P-b_u\right)\bmod P$ ，
$\hspace{23pt}\bullet\,$ 若从点 $v$ 走向点 $u$ ，那你在点 $v$ 时圆盘的指针必须指向 $\left(c+P-b_v\right)\bmod P$ 。
$\hspace{15pt}$ 注意，经过边时不能调整指针。

$\hspace{15pt}$ 求从点 $1$ 到点 $n$ 的最小代价，不可达输出 $-1$ 。

输入描述:

第一行输入三个整数 。
第二行输入  个整数 ，表示第  个点的颜色偏转值。
接下来  行，第  行输入三个整数 ，表示第  条边双向连接点  和点 ，颜色为 。
图可能不连通、可能存在重边。不存在自环。

输出描述:

若点  无法到达点 ，输出 ；否则，输出一个整数，表示从点  到点  的最小代价。

示例1

输入

复制

5 7 20
10 7 10 16 15
1 2 3
2 3 2
1 4 13
4 5 10
3 4 1
2 5 19
1 5 19

输出

复制

说明

在这个样例中，初始图如下图所示，最优路线为 。

示例2

输入

复制

3 1 6
2 3 3
1 2 2

输出

复制

-1