Jim 计划去拜访他住在山区城镇的一位好朋友。首先，他从家乡出发前往目的地城镇，这被称为“去程阶段”。然后，他返回家乡，这被称为“回程阶段”。你需要编写一个程序，寻找这次旅行的最小总花费，即去程阶段和回程阶段的花费之和。

这里有一个包含这两个城镇在内的城镇网络。网络中的每条道路都是单向的，即只能沿着指定的方向行驶。每条道路的通行都需要一定的花费。

除了道路的花费外，途径每个城镇时还必须支付指定的费用。然而，由于这是该城镇的签证费，因此在第二次或之后再次访问同一城镇时，无需重复支付该费用。

每个城镇的海拔（高度）是给定的。在去程阶段，禁止使用下坡路。也就是说，当从城镇 $a$ 前往 $b$ 时，$a$ 的海拔不能大于 $b$ 的海拔。在回程阶段，以类似的方式禁止使用上坡路。如果 $a$ 和 $b$ 的海拔相同，则从 $a$ 到 $b$ 的道路在两个阶段都可以使用。

输入格式

输入由多个数据集组成，每个数据集的格式如下：

$$n \quad m$$ $$d_2 \quad e_2$$ $$d_3 \quad e_3$$ $$\vdots$$ $$d_{n-1} \quad e_{n-1}$$ $$a_1 \quad b_1 \quad c_1$$ $$a_2 \quad b_2 \quad c_2$$ $$\vdots$$ $$a_m \quad b_m \quad c_m$$

数据集中的每个输入项都是非负整数。同行输入项之间用空格分隔。

$n$ 是网络中城镇的数量。$m$ 是（单向）道路的数量。你可以认为不等式 $2 \le n \le 50$ 和 $0 \le m \le n(n - 1)$ 成立。城镇编号为 $1$ 到 $n$（闭区间）。城镇 $1$ 是 Jim 的家乡，城镇 $n$ 是目的地城镇。

$d_i$ 是城镇 $i$ 的签证费，$e_i$ 是它的海拔。你可以认为对于 $2 \le i \le n - 1$，满足 $1 \le d_i \le 1000$ 且 $1 \le e_i \le 999$。城镇 $1$ 和 $n$ 不收取签证费。城镇 $1$ 的海拔为 $0$，城镇 $n$ 的海拔为 $1000$。多个城镇可能具有相同的海拔，但你可以认为相同海拔的城镇不超过 $10$ 个。

第 $j$ 条道路是从城镇 $a_j$ 到 $b_j$，花费为 $c_j$（$1 \le j \le m$）。你可以认为 $1 \le a_j \le n$，$1 \le b_j \le n$ 且 $1 \le c_j \le 1000$。你可以直接从 $a_j$ 走到 $b_j$，但不能从 $b_j$ 走到 $a_j$，除非另有一条从 $b_j$ 到 $a_j$ 的道路。不存在两条连接相同城镇对且方向相同的道路，即对于任意 $i$ 和 $j$（$i \ne j$），满足 $a_i \ne a_j$ 或 $b_i \ne b_j$。不存在连接城镇自身的道路，即对于任意 $j$，满足 $a_j \ne b_j$。

最后一个数据集后面紧跟一行，包含两个零（用空格分隔）。

输出格式

对于输入中的每个数据集，输出一行，包含旅行的最小总花费（包括签证费）。如果无法完成这样的旅行，则输出 -1。

样例

样例输入 1

3 6
3 1
1 2 1
2 3 1
3 2 1
2 1 1
1 3 4
3 1 4
3 6
5 1
1 2 1
2 3 1
3 2 1
2 1 1
1 3 4
3 1 4
4 5
3 1
3 1
1 2 5
2 3 5
3 4 5
4 2 5
3 1 5
2 1
2 1 1
0 0

样例输出 1

7
8
36
-1