旅途

//Dijkstra算法来做
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int M=sc.nextInt();
        int[][] weight=new int[N][N];//保存权值的数组
        int[] value=new int[N];
        for(int i=0;i<N;i++){
            value[i]=sc.nextInt();
        }
        int MAX=2000000;
        //初始化weight
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                weight[i][j]=MAX;
            }
        }
        //sc.nextLine();
        
        for(int i=0;i<M;i++){
            //String[] s=sc.nextLine().split(" ");
            int x=sc.nextInt()-1;
            int y=sc.nextInt()-1;
            weight[x][y]=value[y];
            weight[y][x]=value[x];            
        }
        for(int i=0;i<weight.length;i++){
            weight[i][i]=value[i];
        }
        //weight[0][0]=value[0];
        int[] shortPath=dijkstra(weight,0);
        int min=shortPath[shortPath.length-1];
        System.out.println(min);
    }
    
    public static int[] dijkstra1(int[][] weight,int a){
        int MAX=10000000;
        int n=weight.length;
        int[] shortPath = new int[n];
        int[] visited = new int[n];
        //初始化shortPath
        for(int i=0;i<n;i++){
            shortPath[i]=MAX;
        }
        shortPath[0]=weight[0][0];//还没出发前还有权值
        visited[0]=1;
        
        //核心
        int lastNode=0;//初始化最后一个节点指向开始的节点
        for(int count=1;count<n;count++){
            int dmin=Integer.MAX_VALUE;
            int k=0;//最后节点临时
            for(int i=0;i<n;i++){
                if(visited[i]==0 && shortPath[lastNode]+weight[lastNode][i]<shortPath[i]){
                    shortPath[i]=shortPath[lastNode]+weight[lastNode][i];
                }
                if(visited[i]==0 && shortPath[i]<dmin){
                    dmin=shortPath[i];
                    k=i;
                }
                
            }
            lastNode=k;
            visited[k]=1;
        }
        return shortPath;
    }
    
    public static int[] dijkstra(int[][] weight,int start){
        int vertexNum = weight.length;            //顶点个数
        int[] shortPath=new int[vertexNum];       //保存最短路径值

        String[] path = new String[vertexNum];    //具体路径存在字符串中

        int[] visited = new int[vertexNum];       //顶点i是否已经求过

        //初始化
        shortPath[start]=weight[start][start];
        visited[start]=1;       

        int M=2000000;                               //将2000当成无穷大
        //初始化shortPath数组
        //shortPath[start]=0;
        path[start]=start+"";
        for(int i=0;i<shortPath.length;i++){
            if(i!=start){
                shortPath[i]=M;     
            }
        }

        int lastNode=start;

        for(int count=1;count<vertexNum;count++){
            //第一次，weight[0][1],weight[0][2],weight[0][3],..weight[0][5]中取最小的
            int dmin = Integer.MAX_VALUE;
            int k=0;
            for(int i=0;i<vertexNum;i++){

                if(visited[i]==0 && shortPath[lastNode]+weight[lastNode][i]<shortPath[i]){
                    //拿lastNode到i的值+之前shortPath中lastNode的值 和 对应shortPath比较。小则更新路线
                    //然后再找到一个最小的作为最后的节点
                    shortPath[i]=shortPath[lastNode]+weight[lastNode][i];
                    //路线更新存在path数组中                                     
                    path[i]=path[lastNode]+"-->"+i;                 
                }
                if(visited[i]==0 && shortPath[i]<dmin){
                    dmin=shortPath[i];
                    k=i;                        
                }
            }       
            lastNode=k;
            visited[k]=1;           
        }
        //System.out.println(path[path.length-1]);
        return shortPath;
    }
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			String[] ss=in.nextLine().split(" ");
			int n = Integer.parseInt(ss[0]);
			int m = Integer.parseInt(ss[1]);
			int[] nums = new int[n];
			String[] strs=in.nextLine().split(" ");
			for (int i = 0; i < n; i++) {
				nums[i] = Integer.parseInt(strs[i]);
			}
			int[][] map = new int[n][n];
			for (int i = 0; i < m; i++) {
				String[] str=in.nextLine().split(" ");
				int s = Integer.parseInt(str[0]);
				int b = Integer.parseInt(str[1]);
				map[(Math.min(s, b) - 1)][ (Math.max(s, b) - 1)] = 1;
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j <= i; j++) {
					map[i][j] = -1;
				}
			}
			map[0][0] = nums[0];
			for (int i = 1; i < n; i++) {
				int pro = Integer.MAX_VALUE;
				for (int j = 0; j < i||j==0; j++) {
					if(map[j][j]==-1)
						continue;
					if (map[j][i]==1&&map[j][j]<pro) {
						pro =map[j][j];
					}
				}
				if(pro<Integer.MAX_VALUE){
					map[i][i]=pro+nums[i];
				}
			}
			
			System.out.println(map[n-1][n-1]);
		}
	}

}