U213707 Problem 3小说

由于小 X 是一位奆老， 奆老总是忙得一刻也停不下来。 他刚刚准备完食物， 小 X 童年的挚友小 S 和小 Z 来找他帮忙了…… （这题目长得我想打人）

小 S 和小 Z 十分喜欢看网络写手“25” 的小说， 但由于需要付费才能阅读， 而小 S 和小Z 的零花钱有非常少， 他们只能找小 X 靠黑科技侵入给网站， 把小说给他们。然而小 X 又非常的爱慕虚荣， 他要小 S 和小 Z 到自己家里来取小说。小 S、 小 Z 和小 X 都居住在扬中市， 扬中市共有 n 个小区， m 条主干道（假设每条主干道都是双行线） 。 小 S 家住在 1 号小区， 小 X 家住在 n 号小区。 小 S 每经过一条主干道需要耗费 z 点体力， 但由于小 S 的人脉非常广， 每当他到达一个小区， 他都会和好友攀谈直到体力回满。 由于小 Z 也希望能看到小说， 所以他答应帮助小 S k 次， 这 k 次小 S 经过主干道不需要耗费体力。由于小 S 生性懒惰， 他希望耗费最少的体力到达小 X 家， 请问他最少耗费多少体力？ 注意： 如果小 S 到小 X 家可以一路上都由小 Z 背着， 那么体力上限为 0；如果小 S 到不了小 X 家， 小 S 会很伤心， 体力上限为-1；

第 1 行三个整数 n,m,k， 意思如题目描述。 第 2 到第 n+1 行是 x,y,z 指走连接 x 号小区和 y 号小区的主干道要耗费 z 点体力

一行一个整数， 表示小 S 最少耗费的体力。

对于 30%的数据： n