暂无测试数据。

给定一张图，有 $n$ 个点 $m$ 条双向边组成，DD 目前在 $1$ 号点上要到 $n$ 号点去，这 $n$ 个点中有一些点上有机器人，机器人和 DD 的速度都是每秒可以走一个单位长度，这些机器人都是 AI 操控采取最优策略来拦截 DD，DD 每碰到一个机器人就会扣一滴生命值（一个点上碰到 $x$ 个就扣 $x$ 滴生命值），她想知道从 $1$ 号点到 $n$ 号点最少要扣多少生命值。

输入格式

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

第二行 $n$ 个整数，$a_i$ 表示 $i$ 号点上有 $a_i$ 个机器人

接下来 $m$ 行，每行三个整数，分别表示该边的起点、终点和长度

输出格式

输出最少要扣多少生命值

数据范围

对于 $30\%$ 的数据，$2 \leq n \leq 10, 1 \leq m \leq 20$

对于 $50\%$ 的数据, $2 \leq n \leq 500, 1 \leq m \leq 1000$

对于 $100\%$ 的数据，$1 \leq u_i,v_i \leq n, 2 \leq n \leq 10^5,1 \leq m \leq 5*10^5,1 \leq dis_i,a_i \leq 10^9$

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