题目描述

在该国有 $n$ 个城市和 $m$ 条带权双向道路连接它们。每个城市都有一支军队。第 $i$ 个城市的军队由 $a_i$ 名士兵组成。现在士兵开始同时游荡。游荡后，每名士兵必须要么留在自己的城市，要么走到任意一座城市，走到城市花费的时间为走过的路径长度。

检查在游荡后，第 $i$ 个城市是否可能最多有 $b_i$ 名士兵，并求出满足条件所需的最短时间。

输入格式

输入 输入的第一行包含两个整数 $n$ 和 $m$ $( 1 ≤ n ≤ 200 , 0 ≤ m ≤ 1500 )$。 下一行包含 n 个整数 $a_1, a_2, \cdots, a_n ( 0 ≤ a_i ≤ 100 )$。

再下一行包含 $n$ 个整数 $b_1, b_2, \cdots, b_n ( 0 ≤ b_i ≤ 1000 )$。

接下来有 $m$ 行，每行包含三个整数 $p,q,w$ $( 1 ≤ p, q ≤ n,1\le w\le 1000, p ≠ q )$，表示城市 $p$ 和 $q$ 之间有一条长度为 $w$ 的无向道路。

输出格式

如果无法满足条件，则输出 $-1$。 否则输出满足条件所需的最短时间。

样例 #1

样例输入 #1

3 4 
7 0 2
2 4 6
1 2 40 
3 2 70 
2 3 90 
1 3 120

样例输出 #1

110