题目描述

C 国由 $n$ 座城市与 $m$ 条有向道路组成，城市与道路都从 $1$ 开始编号，经过 $i$ 号道路需要 $t_i$ 的费用。

现在你要从 $1$ 号城市出发去 $n$ 号城市，你可以施展最多 $k$ 次魔法，使得通过下一条道路时，需要的费用变为原来的相反数，即费用从 $t_i$ 变为 $-t_i$。请你算一算，你至少要花费多少费用才能完成这次旅程。

注意：使用魔法只是改变一次的花费，而不改变一条道路自身的 $t_i$；最终的费用可以为负，并且一个城市可以经过多次（包括 $n$ 号城市）。

输入格式

输入的第一行有三个整数，分别代表城市数 $n$，道路数 $m$ 和魔法次数限制 $k$。

第 $2$ 到第 $(m + 1)$ 行，每行三个整数。第 $(i + 1)$ 行的整数 $u_i, v_i, t_i$ 表示存在一条从 $u_i$ 到 $v_i$ 的单向道路，经过它需要花费 $t_i$。

输出格式

输出一行一个整数表示最小的花费。

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

-8

2 2 2
1 2 10
2 1 1

-19

提示

输入输出样例 1 解释

依次经过 $1$ 号道路、$2$ 号道路、$3$ 号道路，并在经过 $1,2$ 号道路前使用魔法。

输入输出样例 2 解释

依次经过 $1$ 号道路、$2$ 号道路、$1$ 号道路，并在两次经过 $1$ 号道路前都使用魔法。

数据规模与约定

本题共 $20$ 个测试点，各测试点信息见下表。

对于【无环】一栏为“是”的测试点，保证给出的图是一张有向无环图，否则不对图的形态做任何保证。

对于全部的测试点，保证：

• $1 \leq n \leq 100$，$1 \leq m \leq 2500$，$0 \leq k \leq 10^6$。
• $1 \leq u_i, v_i \leq n$，$1 \leq t_i \leq 10^9$。
• 给出的图无重边和自环，且至少存在一条能从 $1$ 到达 $n$ 的路径。

**民间数据使用 CYaRon 在 5 分钟内生成。如果发现数据有问题，请在讨论版发帖或私信