说明

gsy 所在的国家有  n  个城市，城市之间有  m  条双向道路连接，不同道路长度可能不同

在某些城市中存在一些坏人，这些坏人正在追赶 gsy，这里我们认为所有人的移动速度每秒移动  1  单位长度

gsy 现在在  1  号城市，她想要逃到  n  号城市，而所有坏人也会采取最优策略去拦截 gsy

如果某一个时刻当 gsy 到达某个城市时，同样有坏人在这个时刻到达了这个城市，那么 gsy 就会受到伤害

gsy 每碰到一个坏人就会失去一点生命值，同时每个坏人只会对 gsy 造成一次伤害

现在 gsy 想知道她应该怎么选择路径，可以使得自己扣的生命值最少？

输入格式

第一行两个整数分别表示  n,m 

第二行  n  个整数， ai  表示  i  号城市一开始有  ai  个坏人

接下来  m  行，每行三个整数  xi, yi, vi ，表示在  xi  号城市和  yi  号城市之间存在一条长度为  vi  的道路

对于  100%  的数据， 1 <= ui,vi <= n, 2 <= n <= 10^5,1 <= m <= 5*10^5,1 <= disi,ai <= 10^9 

输出格式

输出 gsy 最少要扣多少生命值

样例

4 6
1 2 3 4 
1 2 1
2 3 2
3 4 1 
1 4 2
2 4 10
4 4 3

8