题目描述

灾区需要物资。物资网络中有 $n$ 个节点，其中 $1$ 号节点是总部（唯一的物资来源），$n$ 号节点是灾区（唯一的物资去向），其余节点都是转运站。

网络中有 $m$ 条单向运输线路，第 $j$ 条线路从 $u_j$ 通往 $v_j$，每秒最多通过 $c_j$ 单位物资。

除了线路容量之外，每个节点本身也有处理能力上限：$i$ 号节点每秒最多处理 $p_i$ 单位物资，即经过它的物资总量不能超过 $p_i$。总部与灾区的上限由输入给出，保证不会成为瓶颈。

求每秒最多能有多少单位物资从总部送达灾区。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $p_1\sim p_n$。

接下来 $m$ 行，每行三个整数 $u_j,v_j,c_j$。保证 $u_j\ne v_j$。

输出格式

一行一个整数，表示每秒最多送达灾区的物资量。

输入输出样例 #1

输入 #1

4 4
1000000000 3 5 1000000000
1 2 4
1 3 10
2 4 3
3 4 4

输出 #1

7

说明

样例中 $2$ 号转运站每秒只能处理 $3$ 单位物资，$3$ 号可以处理 $5$ 单位，到达灾区的物资总量上限为 $3+4=7$。

数据范围

• 对于 $100\%$ 的数据，$2\le n\le 500$，$0\le m\le 5000$，$1\le p_i,c_j\le 10^9$。