有一天，上帝来到人间。他见到的第一个人是出题人，发现出题人的智商奇低，十分伤心，于是决定毁灭世界。就在这危急关头，出题人突然说：“不，我只是人间最菜的。我知道一个人他智商通天，他叫硕哥。”于是，上帝让出题人去找他，并且拍一张照片给上帝，以证明是存在毛发浓密的顶级程序员的。但是，上帝的耐心并不好，所以你只有1s~10s帮助智障的出题人解决这个问题。
出题人目前在明理楼，你可以视为1号节点，目前时刻为0。
硕哥在宿舍，你可以视为n号节点。
出题人到硕哥的位置之间，有一些路口。这些路口之间有一些无向道路，出题人是个肥宅，他经过每条边要使用不同的时间。
但是，由于上帝的震怒，一些路口变得不稳定起来，所以很多路口在某个时间节点会崩塌，假设一个路口会在t时刻崩塌的话，那么怕死的智障出题人只能在任何一个小于t的时间点呆在这里。
现在给出道路关系图和每个节点崩塌的时间，求出题人到硕哥所在位置的最短时间，如果出题人无法找到硕哥，输出-1。
输入格式
第一行一个正整数n和一个正整数m，分别表示节点数和无向道路数目
第二行有用空格隔开的n个正整数，表示每个节点的崩塌时间
第三行到第m+2行 每行三个正整数a,b,c表示a节点到b节点之间有一条耗时为c的无向道路
ps:可能存在重边和自环
输出格式
输出一个整数 表示出题人到硕哥所在位置的最短时间，如果出题人无法找到硕哥，输出-1。

输入样例1

4 7
10 3 1 6
1 2 3
1 1 4
1 4 7
1 2 2
2 4 3
1 3 1
3 4 1

输出样例1

5

样例解释
1 1 4 表示存在1到1的自环
1 2 2和1 2 3表示1到2之间有两条边，耗时分别为2和3，即重边。
出题人最终的行走路线是1到2，耗时2。然后再从2走到4，耗时3。所以总耗时是2+3=5
出题人不能从1走到3再从3走到4，因为1走到3时，3号路口已经崩塌。

输入样例2

2 1
1 2
1 2 2

输出样例2

-1

输出解释
出题人无法找到硕哥并完成偷拍，因为他刚到他的面前，宿舍就崩塌了。
数据范围
对于50%的数据，n<4,m<10,其他所有数据（包括答案）都在int范围内,时限1s
对于100%的数据，n<8,m<20,其他所有数据（包括答案）都在int范围内，时限10s