### 问题描述 给定 $N$ 个点 $M$ 条边的无向带权连通图，每个节点上有一个商店，第 $i$ 个商店有 $a_i$ 件商品。 对于一条无向边 $(u,v,w)$，可以花费 $w$ 的代价将一件商品从 $u$ 运送到 $v$ 或花费 $w$ 的代价将一件商品从 $v$ 运送到 $u$，现在要求所有商店的商店商品数量相同，请你求出最小代价。 ### 输入格式 第一行包含 $2$ 个正整数 $N,M$。 第二行包含 $N$ 个整数，第 $i$ 个表示 $a_i$。 之后 $M$ 行，每行给定 $u_i,v_i,w_i$，表示图中的一条边。 ### 输出格式 输出 $1$ 行，包含一个整数，表示答案。 ### 样例输入 ```text 4 3 1 2 3 6 1 2 1 2 3 1 3 4 1 ``` ### 样例输出 ```text 8 ``` ### 样例解释 最优方案为 $4$ 号点调配 $3$ 件商品给 $3$ 号点，$3$ 号点调配 $3$ 件商品给 $2$ 号点，$2$ 号点调配 $2$ 件商品给 $1$ 号点，总代价为 $8$。 ### 评测数据规模 对于所有测评数据，$1 \leq N \leq 500,1 \leq M \leq 1000,0 \leq a_i \leq 1000,0 \leq w_i \leq 500,N|\sum_{i=1}^N a_i$。