T426519 「YAC Round 5」The World 世界

 > **蕾米莉亚**：对了，咲夜不想要不老不死吗？这样就能和我一直在一起了。 **咲夜**：我一生都是会死的人类哦。放心，只要还活着就会一直陪着大小姐。

十六夜咲夜拥有操纵时间程度的能力和停止时间程度的能力，煮饭、打扫、洗衣服、看小孩（500岁的吸血鬼萝莉小女孩？）、投飞刀、女仆所应该做的事情全能迅速且完美地做好。 幻想乡由 $N$ 个地点，$M$ 条 **单向道路** 构成，经过第 $i$ 条道路，需要花费 $t_i$ 的时间。现在咲夜需要去人间之里购买一些今晚与大小姐共进晚餐的食材。咲夜所在的地方是红魔馆，地点编号为 $1$；要去的地方是人间之里，地点编号为 $N$ 。 十六夜咲夜拥有符卡 「The World 世界」，可以使得时间停滞。咲夜 **最多** 可以使用 $K$ 次符卡 「The World 世界」，每次使用符卡可以使得经过的下一条道路消耗的时间变为原来的相反数，也就是说在使用符卡后，花费时间 $t_i$ 的道路变为 $- t_i$ 。 请你帮咲夜计算一下 **最少花费的总时间**。 PS：最终花费总时间可以是负数，一个地点有可能经过多次。使用符卡只是改变一次的时间花费，并不会改变道路本身的 $t_i$。

第一行有三个整数 $N, M, K$，分别表示地点数量 $N$，单向道路数 $M$ 和符卡使用次数限制 $K$。 接下来 $M$ 行，每行三个整数 $u_i, v_i, t_i$。表示存在一条从 $u_i$ 到 $v_i$ 的单向道路，经过它需要花费 $t_i$ 的时间。

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

#### 样例 1 解释 依次经过第 $1$ 条道路、第 $3$ 条道路、第 $2$ 条道路。在经过第 $1,3$ 条道路前使用符卡，最终的时间花费为 $-9$。 #### 样例 2 解释 依次经过第 $1$ 条道路、第 $2$ 条道路、第 $1$ 条道路。在两次经过第 $1$ 条道路前都使用符卡，最终的时间花费为 $-11$。 #### 数据范围与约定 $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$ 的路径。