题目背景：

我好想做嘉然小姐的狗啊。

可是嘉然小姐说她喜欢的是猫，我哭了。

我知道既不是狗也不是猫的我为什么要哭的。因为我其实是一只老鼠。

我从没奢望嘉然小姐能喜欢自己。我明白的，所有人都喜欢理解余裕上手天才打钱的萌萌的狗狗或者猫猫，没有人会喜欢阴湿带病的老鼠。

题目内容：

但是这依然改变不了你对然然的爱，即使你住在下水道里，你也要游过管道，来到嘉然小姐的住处，在她脚下默默地看着她。

枝江市的下水道系统和别的城市不同，它由 $n$ 个节点组成，其中，$1$ 号节点是你所处的位置，$n$ 号节点是嘉然家的下水道。每个节点有一个水位高度 $h_i$，保证每个节点的水位高度各不相同，并且 $1$ 号节点水位最高，$n$ 号节点水位最低。

这 $n$ 个节点由 $m$ 条管道连接，第 $i$ 条管道连接 $u_i,v_i$ 两个节点。由于「水往低处流」，你只能沿着管道从水位高的节点游到水位低的节点，同时游过这管道需要 $t_i$ 的时间。、

你太喜欢然然了，迫不及待地想要见到她。请问你最短需要多长时间才能到达 $n$ 号节点。

输入格式

第一行为空格隔开的两个数 $n, m$。

第二行为空格隔开的 $n$ 个正整数，第 $i$ 个数为 $h_i$，表示第 $i$ 个节点的水位高度。

接下来 $m$ 行，每行为空格隔开 $3$ 个正整数 $u_i, v_i, t_i$，分别表示第 $i$ 条管道连接的两个节点与游过这管道需要的时间。

输出格式：

一行一个整数，表示最短需要的时间。

样例 1 输入：

3 3 3 2 1 1 2 1 3 2 1 1 3 3

样例 1 输出：

2