[NOI Online #1 入门组] 魔法

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$ 个测试点，各测试点信息见下表。 | 测试点编号 | $n \leq$ | $m \leq$ | $k \leq$ | 无环 | | :----------: | :--------: | :---------: | :--------: | :----: | | $1 \sim 2$ | $5$ | $20$ | $0$ | 不保证 | | $3 \sim 4$ | $10$ | $20$ | $50$ | 不保证 | | $5 \sim 6$ | $10$ | $20$ | $0$| 不保证 | | $7 \sim 8$ | $20$ | $200$ | $50$ | 是 | | $9 \sim 10$ | $20$ | $200$ | $0$ | 不保证 | | $11 \sim 12$ | $100$ | $200$ | $50$ | 是 | | $13 \sim 14$ | $100$ | $200$ | $50$ | 不保证 | | $15 \sim 18$ | $100$ | $2500$ | $1000$ | 不保证 | | $19 \sim 20$ | $100$ | $2500$ | $10^6$ | 不保证 | 对于【无环】一栏为“是”的测试点，保证给出的图是一张有向无环图，否则不对图的形态做任何保证。 对于全部的测试点，保证： - $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](https://github.com/luogu-dev/cyaron) 在 5 分钟内生成。如果发现数据有问题，请在讨论版发帖或私信 @[StudyingFather](/user/22030)**