nodgd不喜欢走寻常路。

沙坪坝的地形可以看做一个无向图，包含$n$个节点和$m$条无向边，节点编号为$1\sim n$。其中节点$1$是nodgd的家，节点$n$是NK中学。

经过调查，nodgd认为一些节点和一些边很“寻常”，于是规定了这些节点和边的行走次数上限。为了避免走寻常路，nodgd往返家到学校时经常更换线路，避免超过这些次数上限。

那么问题来了，在不超过次数上限的情况下，nodgd最多可以往返家到学校多少次呢？数据保证次数有限。

第一行两个整数$n,m$，表示节点数、边数。

第二行$n$个整数$a_1,a_2,\dots,a_n$，表示每个节点的次数上限，如果$a_i=0$则表示没有上限。保证$a_1=a_n=0$。

接下来$m$行，每行三个整数$u_i,v_i,b_i$，表示一条连接$u_i,v_i$的无向边，次数上限为$b_i$，如果$b_i=0$表示没有上限。

输出一个整数，表示nodgd可以往返家到学校的次数。

样例数据1如图所示，在不超过次数上限的情况下，可以沿着$1-2-5$走$4$次，沿着$1-2-3-5$走$2$次，沿着$1-3-5$走$6$次，沿着$1-4-5$走$5$次。一共可以往返$\lfloor(4+2+6+5)/2\rfloor=8$次。

所有测试数据，\(n\leq5000\)，\(m\leq 500000\)，$0\leq a_i,b_i\leq1000$，保证没有重边和自环。