【题目描述】

现有一有向图 G，节点编号为 1 … 𝑛。你试图缩短 1 到 n 的最短路，因此你可以在图中任意添加最多一条有向边 𝑖 → 𝑗（其中2 ≤ 𝑖,𝑗 ≤ 𝑛 − 1），边权为 𝑘 × | 𝑖 − 𝑗 |。求你可以得到的从 1 到 n 的最短路。

【输入格式】

第一行三个正整数 n, m, k 以空格隔开。

之后 m 行每行三个正整数 s, t, w,表示 s 到 t 有一条边权为 w 的有向边。

【输出格式】

如果有解，输出一行一个正整数，表示答案；如果无解，输出-1。

【样例输入】

5 3 12
1 2 10
2 3 10
4 5 10

【样例输出】

42

【样例解释】

添加一条边 3 到 4，边权为 12 × | 3 − 4| = 12，最短路为1 → 2 → 3 → 4 → 5 = 10 + 10 + 12 + 10 = 42。

【数据范围】

对于 30%的数据，3 ≤ 𝑛 ≤ 300；

对于 60%的数据，3 ≤ 𝑛 ≤ 5000；

对于 100%的数据，3 ≤ 𝑛 ≤ 100000,1 ≤ 𝑚 ≤ 200000,$1 ≤ 𝑤, 𝑘 ≤ 10^9$ 不保证数据中没有自环和重边。