C1638 [Wannafly冬令营2018Day1]爬爬爬山

爬山是 $wls$ 最喜欢的活动之一。

在一个神奇的世界里，一共有 $n$ 座山，$m$ 条路。

$wls$ 初始有 $k$ 点体力，在爬山的过程中，他所处的海拔每上升 $1m$，体力会减 $1$ 点，海拔每下降 $1m$，体力会加一点。

现在 $wls$ 想从 $1$ 号山走到 $n$ 号山，在这个过程中，他的体力不能低于 $0$，所以他可以事先花费一些费用请 $dls$ 把某些山降低，将一座山降低 $l$ 米需要花费 $l*l$ 的代价，且每座山的高度只能降低一次。因为 $wls$ 现在就在 $1$ 号山上，所以这座山的高度不可降低。

$wls$ 从 $1$ 号山到 $n$ 号山的总代价为降低山的高度的总代价加上他走过的路的总长度。

$wls$ 想知道最小的代价是多少。

样例输入 1

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

样例输出 1

6