题目描述

众所周知，中间商赚差价，总是能赚很多钱，而最近新开了一款名为 《中间商》 的游戏

在这个游戏中，玩家需要经过不断的和其他人交易或者合成物品，最终获得能够让自己获胜的道具

现在 ztm 为了比别人更快的通关游戏，于是他准备给自己开个金手指

假设现在总共有 $n$ 个 NPC，每个人手里有一种物品，第 $i$ 个人手里的物品编号为 $i$

现在 ztm 的目标是获得 $1$ 号物品，来使得自己获胜

游戏过程中，玩家有两种方式可以获得物品

1. 直接问物品持有人买，购买一件第 $i$ 种物品需要花费 $v_i$ 的金钱
2. 尝试用两件道具合成一件新的物品，游戏中共有 $m$ 条不同的合成公式

ztm 可以在游戏开始时利用金手指修改自己原本为 $0$ 的金钱，但是他又不想作弊的太明显

所以他想知道，他最少给自己多少初始金钱，可以使得自己经过不断操作获得 $1$ 号物品？

输入格式

输入第一行包含两个整数 $n,m$，表示有 $n$ 个人和 $m$ 条合成公式 第二行有 $n$ 个整数，分别为 $v_1,v_2,v_3...$ 分别表示每个物品的价格 接下来 $m$ 行，每行包含三个整数 $x_i,y_i,z_i$ 表示一条合成公式，含义为 $x$ 号物品可以由 $y$ 物品加 $z$ 号物品合成得到

输出格式

输出一个整数表示最少的初始金钱

数据范围

对于 $40\%$ 的数据：$1 \leq n,m \leq 100$ 对于 $100\%$ 的数据：$1 \leq n \leq 10^4, 1 \leq m \leq 10^5, 0 \leq v_i \leq 10^9$ 输入保证$(1 \leq x_i,y_i,z_i \leq n, x_i \not{=} y_i \not {=} z_i)$

样例输入

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

样例输出

2