### 问题描述 在战争时期，兵粮的输送是至关重要的任务。每一次胜利的打击都需要有足够的食物和弹药作为后盾，我们的兵粮输送团队已经做好了准备，随时准备将粮草、军火运往前线。 小郑作为指挥官，管辖着 $N$ 个连，这 $N$ 个连有着 $M$ 条双向路径连接，小郑需要统筹调配兵粮物资。 每个连对于物资的需求情况为 $a[i]$，如果大于 $0$ 则说明该连物资富裕，可以调配给其他连 $a[i]$ 单位资源。 如果 $a[i]$ 小于 $0$ 则说明该连物资缺乏，需要从其他地方调配 $a[i]$ 单位资源到该连。 每个单位的物资运输代价就是运输距离，请你帮帮小郑，求出所有物资缺乏连得到足够资源的最少运输代价和。 ### 输入格式 第一行输入两个整数 $N$、$M$，分表代表连的数量和路径数量。 随后一行输入 $N$ 个整数，分别代表该连物资的需求量 $a[i]$。 随后 $M$ 行，每行输入三个整数 $U$、$V$、$W$，表示 $U$ 和 $V$ 之间有一条距离为 $W$ 的双向路径。 ### 输出格式 输出 $1$ 个整数，表示使所有紧缺物资的连得到足够的资源的最小运输代价和；如果无法满足要求，则输出 $-1$。 ### 样例输入 ```text 3 3 10 0 -5 1 2 1 2 3 3 1 3 5 ``` ### 样例输出 ```text 20 ``` ### 样例说明 样例中，位置 $1$ 要运送给位置 $3$ 五个单位的资源，此时位置 $1$ 到位置 $3$，通过 $1\Rightarrow>2\Rightarrow 3$ 距离为 $4$，故总代价为 $20$。 ### 评测数据规模 对于所有评测数据，$0 \lt N、M、U、V \lt 500$，$0 \lt W \lt 10^3$，$-10^3 \lt a[i] \lt 10^3$。