给定一张图，有 n 个点 m 条双向边组成，DD 目前在 1 号点上要到 n 号点去，这 n 个点中有一些点上有机器人，机器人和 DD 的速度都是每秒可以走一个单位长度，这些机器人都是 AI 操控采取最优策略来拦截 D，D 每碰到一个机器人就会扣一滴生命值（一个点上碰到 x 个就扣 x 滴生命值），她想知道从 1 号点到 n 号点最少要扣多少生命值。
给定一张图，有 n 个点 m 条双向边组成，DD 目前在 1 号点上要到 n 号点去，这 n 个点中有一些点上有机器人，机器人和 DD 的速度都是每秒可以走一个单位长度，这些机器人都是 AI 操控采取最优策略来拦截 D，D 每碰到一个机器人就会扣一滴生命值（一个点上碰到 x 个就扣 x 滴生命值），她想知道从 1 号点到 n 号点最少要扣多少生命值。
第一行两个整数分别表示n,m
第二行 n 个整数， ai 表示 i 号点上有 ai 个机器人
接下来 m 行，每行三个整数，分别表示该边的起点、终点和长度
输出最少要扣多少生命值
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
对于 30% 的数据， 2≤n≤10,1≤m≤20
对于 50% 的数据, 2≤n≤500,1≤m≤1000
对于 100% 的数据， 1≤ui,vi≤n,2≤n≤105,1≤m≤5∗105,1≤disi,ai≤109
******普及模拟题2019-1-C*****