CF102A.Clothes

A little boy Gerald entered a clothes shop and found out something very unpleasant: not all clothes turns out to match. For example, Gerald noticed that he looks rather ridiculous in a smoking suit and a baseball cap.

Overall the shop sells n clothing items, and exactly m pairs of clothing items match. Each item has its price, represented by an integer number of rubles. Gerald wants to buy three clothing items so that they matched each other. Besides, he wants to spend as little money as possible. Find the least possible sum he can spend.

一个小男孩杰拉尔德走进一家服装店，发现了一件非常不愉快的事情：并非所有服装都能互相搭配。例如，杰拉尔德注意到，自己穿着燕尾服和棒球帽时看起来相当滑稽。

这家店铺总共出售 $n$ 件服装，其中恰好有 $m$ 对服装可以互相搭配。每件服装都有其价格，以整数卢布表示。杰拉尔德希望购买三件服装，使得这三件服装两两之间均能互相搭配。此外，他希望花费尽可能少的钱。请找出他可能花费的最少金额。

The first input file line contains integers n and m — the total number of clothing items in the shop and the total number of matching pairs of clothing items ().

Next line contains n integers a__i (1 ≤ a__i ≤ 106) — the prices of the clothing items in rubles.

Next m lines each contain a pair of space-separated integers u__i and v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i). Each such pair of numbers means that the u__i-th and the v__i-th clothing items match each other. It is guaranteed that in each pair u__i and v__i are distinct and all the unordered pairs (u__i, v__i) are different.

第一行输入包含两个整数 $n$ 和 $m$ —— 分别表示商店中服装总数以及相互匹配的服装对总数（）。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^6$）—— 表示各服装的价格（单位：卢布）。

接下来的 $m$ 行，每行包含一对以空格分隔的整数 $u_i$ 和 $v_i$（$1 \le u_i,\,v_i \le n$，且 $u_i \ne v_i$）。每对数字表示第 $u_i$ 件与第 $v_i$ 件服装可以相互搭配。保证在每对中 $u_i$ 与 $v_i$ 互不相同，且所有无序对 $(u_i,\,v_i)$ 互不重复。

Print the only number — the least possible sum in rubles that Gerald will have to pay in the shop. If the shop has no three clothing items that would match each other, print "-1" (without the quotes).

输出唯一一个数字——Gerald 在商店中需要支付的最少金额（单位：卢布）。如果商店中不存在三件能相互匹配的服装，则输出 “-1”（不带引号）。

In the first test there only are three pieces of clothing and they all match each other. Thus, there is only one way — to buy the 3 pieces of clothing; in this case he spends 6 roubles.

The second test only has three pieces of clothing as well, yet Gerald can't buy them because the first piece of clothing does not match the third one. Thus, there are no three matching pieces of clothing. The answer is -1.

In the third example there are 4 pieces of clothing, but Gerald can't buy any 3 of them simultaneously. The answer is -1.

在第一个测试中，仅有三件衣物，且它们彼此都相配。因此，只有一种方案——购买这三件衣物；此时他花费 6 卢布。

第二个测试中也仅有三件衣物，但杰拉尔德无法购买它们，因为第一件衣物与第三件衣物不相配。因此，不存在三件彼此相配的衣物。答案为 -1。

第三个例子中有 4 件衣物，但杰拉尔德无法同时购买其中任意 3 件。答案为 -1。