爬山是Reverie最喜欢的活动之一。
黄龙山一共有n座小山，小山之间有m条路。
Reverie初始有k点体力，在爬山的过程中，她所处的海拔每上升1m，体力会减1点，海拔每下降1m，体力会加1点。
现在Reverie想从1号山走到n号山，在这个过程中，她的体力不能低于0。
所以她可以事先花费一些费用请挖掘机把某些山降低，将一座山降低l米需要花费l×l的代价，且每座山的高度只能降低一次。
因为Reverie现在就在1号山上，所以这座山的高度不可降低。
Reverie从1号山到n号山的总代价为降低山的高度的总代价加上她走过的路的总长度。
Reverie想知道最小的代价是多少。

第一行三个整数n，m，k。
接下来一行n个整数，分别表示第1道n座山的高度。
接下来m行，每行三个整数x，y，z表示山x和山y之间有一条长度为z的双向道路。
经过每条路时海拔是一个单调上升或下降的过程。
数据保证1号山和n号山联通。
1≤n,k,h,z≤10^5
1≤m≤2×10^5
1≤x,y≤n
x≠y

一行一个整数表示答案。

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

6

Wannacry-02