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.

Input

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 (<image>).

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

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

Output

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).

Examples

Input

3 3
1 2 3
1 2
2 3
3 1


Output

6


Input

3 2
2 3 4
2 3
2 1


Output

-1


Input

4 4
1 1 1 1
1 2
2 3
3 4
4 1


Output

-1

Note

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.
import java.io.*;
import java.util.*;
import java.math.*;
import static java.lang.Math.*;

public class Main implements Runnable {

    StreamTokenizer in;
    BufferedReader reader;
    PrintWriter out;
    StringTokenizer tok;
    boolean timus = System.getProperty("ONLINE_JUDGE")!=null;
    boolean codeforces = true;
    final double eps = 1e-9;
    
    public static void main(String[] args) throws Exception {
        new Thread(new Main()).start();
    }
    
    @Override
    public void run() {
        try {
            if (codeforces) {
                reader = new BufferedReader(new InputStreamReader(System.in));
                in = new StreamTokenizer(reader);
                out= new PrintWriter (new OutputStreamWriter(System.out));
                tok = new StringTokenizer("");
                solve();
                out.flush();
            } else
            if (!timus) {
                long begMem = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
                long t1 = System.currentTimeMillis();
                reader = new BufferedReader(new InputStreamReader(System.in));
                in = new StreamTokenizer(reader);
                out= new PrintWriter (new OutputStreamWriter(System.out));
                tok = new StringTokenizer("");
                solve();
                long endMem = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
                out.flush();
                long t2 = System.currentTimeMillis();
                System.out.println("Time:"+(t2-t1));
                System.out.println("Memory:"+(endMem-begMem));
                System.out.println("Total memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()));
            } else {
                reader = new BufferedReader(new FileReader("input.txt"));
                in = new StreamTokenizer(reader);
                out= new PrintWriter (new FileWriter("output.txt"));
                tok = new StringTokenizer("");
                solve();
                out.flush();
                out.close();
            }
        }
        catch (Exception ex) {
            System.out.println("fail");
            System.exit(1);
        }
    }
    
    public class Chess {
        String coord;
        
        public Chess(String s){
            this.coord=s;
        }
        
        public int toInteger(char s) {
            if (s=='a'||s=='A') return 1;
            else if (s=='b'||s=='B') return 2;
            else if (s=='c'||s=='C') return 3;
            else if (s=='d'||s=='D') return 4;
            else if (s=='e'||s=='E') return 5;
            else if (s=='f'||s=='F') return 6;
            else if (s=='g'||s=='G') return 7;
            else if (s=='h'||s=='H') return 8;
            else return -1;
        }
        
        public String toString(int s) {
            if (s==1) return "a";
            else if (s==2) return "b";
            else if (s==3) return "c";
            else if (s==4) return "d";
            else if (s==5) return "e";
            else if (s==6) return "f";
            else if (s==7) return "g";
            else if (s==8) return "h";
            else return "0";
        }
        
        public pair getPair() {
            String j="";
            j+=coord.charAt(1);
            pair p = new pair(toInteger(coord.charAt(0)),Integer.parseInt(j));
            if (p.x!=-1)
            return p; else
                return new pair(0,0);
        }
        
        public String returnPair(int a,int b) {
            String s = toString(a)+b;
            return s;
        }
    }
    
    public int nextInt() throws Exception {
        in.nextToken();
        return (int) in.nval;
    }
    
    public String next() throws Exception {
        in.nextToken();
        return in.sval;
    }
    
    public String nextLine() throws Exception {
        return reader.readLine();
    }
    
    public String nextString() throws Exception {
        while (!tok.hasMoreTokens())
            tok = new StringTokenizer(reader.readLine());
        return tok.nextToken();
    }
    
    public long nextLong() throws Exception {
        return Long.parseLong(nextString());
    }
    
    public class pair {
        int x;
        int y;
        
        public pair(int x, int y) {
            this.x=x;
            this.y=y;
        }
    }
    
    public int gcd(int a, int b) {
        if (a== 0||b==0) return 1;
        if (a<b) {
                int c=b;
                b=a;
                a=c;
        }
        while (a%b!=0) {
                a =a%b;
                if (a<b) {
                        int c=b;
                        b=a;
                        a=c;
                }
        }
        return b;
    }
    
     public int pow(int a, int n) {
         if (n==0) return 1;
         int k=n, b=1, c=a;
         while (k!=0) {
                 if (k%2==0) {
                         k/=2;
                         c*=c;
                 } else {
                         k--;
                         b*=c;
                 }
         }
         return b;
     }
    
    public int lcm(int a, int b) {
        return a*b/gcd(a,b);
    }
    
    public class pairs implements Comparable<pairs> {
        int x;
        int y;
        
        public pairs(int x, int y) {
            this.x=x;
            this.y=y;
        }

        @Override
        public int compareTo(pairs obj) {
            if (this.x<((pairs)obj).x) return 1;
            else if (this.x==(obj).x&&this.y<(obj).y) return 1;
            else if (this.x==(obj).x&&this.y==(obj).y)return 0; else
                return -1;
        }   
    }
    
    public int[] findPrimes(int x) {
        boolean[] erat = new boolean[x-1];
        List<Integer> t = new ArrayList<Integer>();
        int l=0, j=0;
        for (int i=2;i<x; i++) {
                if (erat[i-2]) continue;
                t.add(i);
                l++;
                j=i*2;
                while (j<x) {
                        erat[j-2]=true;
                        j+=i;
                }
        }
        int[] primes = new int[l];
        Iterator<Integer> iterator = t.iterator();
        for (int i = 0; iterator.hasNext(); i++) {
                primes[i]=iterator.next().intValue();
        }
        return primes;
    }   
    
    public void solve() throws Exception {
        int n=nextInt();
        int m=nextInt();
        int [] a = new int [n];
        for (int i=0; i<n;i++) {
            a[i]=nextInt();
        }
        int [][] b = new int [n][n];
        for (int i=0; i<m;i++) {
            int q=nextInt()-1;
            int w=nextInt()-1;
            b[q][w]=1;
            b[w][q]=1;
        }
        int min=Integer.MAX_VALUE;
        for (int i=0; i<n;i++) {
            for (int j=0; j<n;j++) {
                for (int k=0; k<n;k++) {
                    if (b[k][i]==1&&b[i][j]==1&&b[k][j]==1&&i!=j&&i!=k&&j!=k) {
                        min = min(a[i]+a[k]+a[j],min);
                    }
                }
            }
        }
        out.println(min==Integer.MAX_VALUE? -1:min);
    }
    

}
